Ferume은 나에게 $O(n\sqrt{n} \log n)$보다 빠르게 이 문제를 해결할 수 있는지 물었다. 그리고 나는 할 수 있었다! 이 문제를 만들어 지루한 풀이로 남지 않게 해준 그에게 감사한다.

$S$를 음이 아닌 정수들을 포함하는 다중집합(multiset)이라고 하자. $S$에 대해 다음 연산을 원하는 횟수만큼(0번 포함) 수행할 수 있다: $S$에 $x$가 적어도 두 번 이상 존재하도록 하는 $x$를 선택하여, 그중 하나를 삭제하고 $(x - 1)$ 또는 $(x + 1)$을 하나 삽입한다(단, $(x - 1)$은 음이 아닌 경우에만 삽입할 수 있다). $F(S)$를 이러한 연산을 통해 얻을 수 있는 최대 mex라고 하자. 여기서 $\text{mex}(S)$는 $S$에 포함되지 않은 가장 작은 음이 아닌 정수를 의미한다.

길이가 $n$인 배열 $a$와 $q$개의 쿼리 $[l; r]$이 주어진다. 각 쿼리에 대해 $F(\{a_l, a_{l+1}, \dots, a_r\})$를 구하라.

입력

첫 번째 줄에는 배열의 크기와 쿼리의 개수를 나타내는 두 정수 $n, q$ ($1 \le n, q \le 5 \cdot 10^5$)가 주어진다.

두 번째 줄에는 배열의 정수 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 5 \cdot 10^5$)이 주어진다.

다음 $q$개의 줄에는 $i$번째 쿼리를 나타내는 두 정수 $l_i, r_i$ ($1 \le l_i \le r_i \le n$)가 주어진다.

출력

각 쿼리에 대한 답을 입력에 주어진 순서대로 각 줄에 출력한다.

예제

예제 입력 1

3 3
0 0 2
1 3
2 3
3 3

예제 출력 1

3
1
0

예제 입력 2

3 2
1 2 2
1 2
1 3

예제 출력 2

0
3