题目描述

「H 指数」可以衡量学者论文的数量与引用量。一位学者的「H 指数」为最大的整数 $h$，满足他至少有 $h$ 篇论文被引用了不少于 $h$ 次。

Mirko 一共发表了 $n$ 篇论文，而他有 $q$ 个疑问：如果他只发表了第 $l_i$ 篇至第 $r_i$ 篇论文，他的「H 指数」会是多少？

输入格式

第一行两个整数 $n, q$。

第二行 $n$ 个整数 $p_i$，其中 $p_i$ 表示他的第 $i$ 篇论文的引用量。

接下来 $q$ 行，每行两个整数 $l_i, r_i$，表示一个疑问。

输出格式

共 $q$ 行。每行一个整数，表示一个疑问的答案。

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

提示

数据规模与约定

本题采用捆绑测试。

对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5$，$1 \le p_i \le 2 \times 10^5$，$1 \le l_i \le r_i \le n$。

说明

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2020-2021 CONTEST #6 T5 Index。