[COCI2020-2021#6] Index
题目描述
「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$ 行。每行一个整数,表示一个疑问的答案。
输入输出样例
输入样例 #1
7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7
输出样例 #1
1
3
3
1
2
2
说明
#### 数据规模与约定
**本题采用捆绑测试**。
| Subtask | 分值 | 数据规模与约定 |
| :----------: | :----------: | :----------: |
| $1$ | $20$ | $1 \le n, q \le 10^3$ |
| $2$ | $40$ | $1 \le n, q \le 5 \times 10^4$ |
| $3$ | $50$ | 无附加约定 |
对于 $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](https://hsin.hr/coci/archive/2020_2021/) [CONTEST #6](https://hsin.hr/coci/archive/2020_2021/contest6_tasks.pdf) _T5 Index_**。