Ferume zapytał mnie, czy potrafię rozwiązać to szybciej niż w $O(n\sqrt{n} \log n)$. Okazuje się, że potrafię! Dzięki niemu za stworzenie tego zadania i niepozwolenie mu na istnienie z nudnym rozwiązaniem.

Niech $S$ będzie multizbiorem zawierającym nieujemne liczby całkowite. Możesz wykonać następującą operację na $S$ dowolną liczbę razy (być może zero): wybierz $x$ takie, że w $S$ występują co najmniej dwa wystąpienia $x$, usuń jedno z wystąpień, ale wstaw w zamian jedno wystąpienie $(x - 1)$ lub $(x + 1)$ (możesz wstawić $(x - 1)$ tylko wtedy, gdy jest ono nieujemne). Niech $F(S)$ będzie maksymalnym mex, jaki można osiągnąć za pomocą tych operacji. Tutaj $\text{mex}(S)$ to minimalna nieujemna liczba całkowita, która nie występuje w $S$.

Dana jest tablica $a$ o długości $n$ oraz $q$ zapytań $[l; r]$. Dla każdego zapytania znajdź $F(\{a_l, a_{l+1}, \dots, a_r\})$.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n, q$ ($1 \le n, q \le 5 \cdot 10^5$) — rozmiar tablicy oraz liczbę zapytań. Druga linia zawiera samą tablicę liczb całkowitych $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 5 \cdot 10^5$). Kolejne $q$ linii zawiera dwie liczby całkowite $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — $i$-te zapytanie.

Wyjście

Wypisz odpowiedzi na zapytania w kolejności, w jakiej zostały podane na wejściu, każdą w osobnej linii.

Przykład

Wejście 1

3 3
0 0 2
1 3
2 3
3 3

Wyjście 1

3
1
0

Wejście 2

3 2
1 2 2
1 2
1 3

Wyjście 2

0
3