P7554 [COCI 2020/2021 #6] Index

The "H-index" measures both the number of papers a researcher has and how many citations they received. A researcher's "H-index" is the largest integer $h$ such that they have at least $h$ papers, each cited at least $h$ times. Mirko has published $n$ papers in total, and he has $q$ questions: if he had published only papers from the $l_i$-th to the $r_i$-th, what would his "H-index" be?

The first line contains two integers $n, q$. The second line contains $n$ integers $p_i$, where $p_i$ is the citation count of Mirko's $i$-th paper. The next $q$ lines each contain two integers $l_i, r_i$, representing a question.

Output $q$ lines. Each line contains one integer, the answer to the corresponding question.

#### Constraints and Notes **This problem uses bundled testdata**. | Subtask | Points | Constraints and Notes | | :----------: | :----------: | :----------: | | $1$ | $20$ | $1 \le n, q \le 10^3$ | | $2$ | $40$ | $1 \le n, q \le 5 \times 10^4$ | | $3$ | $50$ | No additional constraints | For $100\%$ of the testdata, $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$. ------------ #### Explanation **The score of this problem follows the original COCI settings, with a full score of $110$**. **Translated from [COCI2020-2021](https://hsin.hr/coci/archive/2020_2021/) [CONTEST #6](https://hsin.hr/coci/archive/2020_2021/contest6_tasks.pdf) _T5 Index_**。 Translated by ChatGPT 5