题目描述

译自 COCI 2020/2021 Contest #6 T5 「Index」

定义一个数列的指数为取一个 $x$，满足有 $x$ 个数大于等于 $x$ 且 $x$ 最大。

现在给您一个长为 $n$ 的数列，有 $q$ 次询问，每次询问一个区间的指数。

输入格式

第一行为两个整数 $n$ 和 $q$。
第二行为 $n$ 个整数 $p_i$。
接下来 $q$ 行，每行两个整数 $l_i, r_i$，表示询问区间 $[l_i, r_i]$ 的指数。

输出格式

输出 $q$ 行，每行一个整数，第 $i$ 行表示 $[l_i, r_i]$ 的指数。

样例

输入

7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7

输出

1
3
3
1
2
2

数据范围与提示

对于所有子任务，有 $1 \le n, q, p_i \le 2 \times 10^5$，$1 \le l_i \le r_i \le n$。