3391: C.Just h-index
题目描述
The h-index of an author is the largest h where he has at least h papers with citations not less than h.
Bobo has published n papers with citations a1, a2, . . . , an respectively. One day, he raises q questions. The i-th question is described by two integers li and ri, asking the h-index of Bobo if has only published papers with citations ali , ali+1, . . . , ari .
输入
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains two integers n and q. The second line contains n integers a1, a2, . . . , an. The i-th of last q lines contains two integers li and ri.
输出
For each question, print an integer which denotes the answer.
Constraint
• 1 ≤ n, q ≤ 105
• 1 ≤ ai ≤ n
• 1 ≤ li ≤ ri ≤ n
• The sum of n does not exceed 250, 000.
• The sum of q does not exceed 250, 000.
样例输入 复制
5 3
1 5 3 2 1
1 3
2 4
1 5
5 1
1 2 3 4 5
1 5
样例输出 复制
2
2
2
3