Problem Description

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 $a_1, a_2, \dots, a_n$ respectively.
One day, he raises $q$ questions. The $i$-th question is described by two integers $l_i$ and $r_i$, asking the $h$-index of Bobo if has *only* published papers with citations $a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$.

Input

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 $a_1, a_2, \dots, a_n$.
The $i$-th of last $q$ lines contains two integers $l_i$ and $r_i$.

Output

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

## Constraint

* $1 \leq n, q \leq 10^5$
* $1 \leq a_i \leq n$
* $1 \leq l_i \leq r_i \leq 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