题目描述

给定一个由 $1$ 到 $N$ 组成的排列 $a_1,a_2,\ldots,a_N$。

如果存在一组下标 $j_1<j_2<\cdots<j_M$，使得对应元素 $a_{j_1},a_{j_2},\ldots,a_{j_M}$ 经过重新排列后 可以成为一段连续整数，那么称这组下标构成一个特殊子序列。更形式化地说，存在一种重新排列方式，使得：

你需要回答 $Q$ 个询问 $(l_i,r_i)$。对于每个询问，求：

• 在下标区间 $[l_i,r_i]$ 对应的子数组中，最长特殊子序列的长度是多少？

更准确地说，我们要求最大的 $M$，使得存在一个特殊子序列满足：

输入格式

第一行包含两个整数 $N,Q$，分别表示数字个数和询问个数。

第二行包含 $N$ 个整数，表示排列 $a_1,a_2,\ldots,a_N$。

接下来 $Q$ 行，每行包含两个整数 $l_i,r_i$。

输出格式

对于每个询问，输出一行一个整数，表示所求特殊子序列的最大长度。

数据范围

• $1 \le N,Q \le 2 \times 10^5$
• $1 \le a_i \le N$
• $1 \le l_i \le r_i \le N$

子任务

通过某个子任务的全部测试后，才能获得该子任务的分数。

样例

输入

4 2
2 4 1 3
1 4
2 4

输出

4
2

样例解释

第一个询问包含了所有数字，它们显然可以重排成 $1,2,3,4$。

第二个询问包含数字 $4,1,3$。我们能选择的最长特殊子序列由数字 $4$ 和 $3$ 组成，它们可以重排成 $3,4$。