Description

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?

Input Format

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 Format

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

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

Hint

Constraints and Notes

This problem uses bundled testdata.

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 CONTEST #6 T5 Index。

Translated by ChatGPT 5