Index

문제

The h-index is an author-level metric that measures both the productivity and citation impact of the publications of a scientist or scholar. It is defined as the maximum value of h such that the given author has published h papers that have each been cited at least h times.

Our Mirko is nearing retirement. In his life he had published n papers and now q times he asks himself the following: “I wonder, what would be my h-index had I only published papers l_i through r_i?”

Help him calculate the answers.

입력

The first line contains integers n and q (1 ≤ n, q ≤ 200 000), the number of papers and the number of questions.

The second line contains n integers p_i (1 ≤ p_i ≤ 200 000), where p_i is the number of citations of the i-th paper.

The following q lines each contain two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n), the endpoints from the i-th question.

출력

Output q lines. In the i-th line output the answer to the i-th 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