레이팅 미적용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.
Subtask 1 (20 points): \(1 \le n\), \(q \le 1000\)
Subtask 2 (40 points): \(1 \le n\), \(q \le 50\,000\)
Subtask 3 (50 points): No additional constraints. Example input 7 6 3 2 3 1 1 4 7 3 4 1 7 1 6 4 5 1 2 5 7 output
Subtask 1 (3 points): —
Subtask 3 (1 points): —
Subtask 2 (2 points): —
The first line contains integers \(n\) and \(q\) (\(1 \le n\), \(q \le 200\,000\)), the number of papers and the number of
questions.
The second line contains \(n\) integers \(p_{i}\) (\(1 \le p_{i} \le 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 \le l_{i} \le r_{i} \le 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