The -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
such that the given author has published
papers that have each been cited at least
times.
Our Mirko is nearing retirement. In his life he had published papers and now
times he asks himself the following:
I wonder, what would be my
-index had I only published papers
through
?
Help him calculate the answers.
Input Specification
The first line contains integers and
, the number of papers and the number of questions.
The second line contains integers
, where
is the number of citations of the
paper.
The following lines each contain two integers
and
, the endpoints from the
question.
Output Specification
Output lines. In the
line output the answer to the
question.
Constraints
Subtask | Points | Constraints |
---|---|---|
1 | 20 | |
2 | 40 | |
3 | 50 | No additional constraints. |
Sample Input 1
7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7
Sample Output 1
1
3
3
1
2
2
Comments