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.
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 lines. In the line output the answer to the question.
|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