A1618.[COCI-2020-2021-contest6]#5 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 li through ri?”
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 pi (1 ≤ pi ≤ 200 000), where pi is the number of citations of the i-th paper.
The following q lines each contain two integers li and ri (1 ≤ li ≤ ri ≤ n), the endpoints from the i-th question.

Output q lines. In the i-th line output the answer to the i-th question.

Subtask Points Constraints
1 20 1 ≤ n, q ≤ 1000
2 40 1 ≤ n, q ≤ 50 000
3 50 No additional constraints.