[AdditionalFile3486.zip](file://AdditionalFile3486.zip?type=additional_file)

#3486. 「COCI 2021.3」Index

标签: 传统 | 时间限制: 2500 ms | 内存限制: 512 MiB |

题目描述

译自 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$。