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 a_li , a_li+1, . . . , a_ri .

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 l_i and r_i.

For each question, print an integer which denotes the answer.

Constraint

• 1 ≤ n, q ≤ 10⁵

• 1 ≤ a_i ≤ n

• 1 ≤ l_i ≤ r_i ≤ 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