Ferume спросил меня, могу ли я решить это быстрее, чем за $O(n\sqrt{n} \log n)$. И оказалось, что могу! Спасибо ему за создание этой задачи и за то, что он не позволил ей остаться со скучным решением.

Пусть $S$ — мультимножество, содержащее неотрицательные целые числа. Вы можете выполнять следующую операцию над $S$ произвольное количество раз (возможно, ноль): выбрать $x$ такое, что в $S$ есть по крайней мере два вхождения $x$, удалить одно из вхождений, но вместо него вставить одно вхождение $(x - 1)$ или $(x + 1)$ (вставить $(x - 1)$ можно только в том случае, если оно неотрицательно). Пусть $F(S)$ — максимальное значение mex, которое можно получить с помощью этих операций. Здесь $\text{mex}(S)$ — это минимальное неотрицательное целое число, которое отсутствует в $S$.

Вам дан массив $a$ длины $n$ и $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$ строк содержат по два целых числа $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — $i$-й запрос.

Выходные данные

Выведите ответы на запросы в том порядке, в котором они перечислены во входных данных, по одному в строке.

Примеры

Входные данные 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