F. Ребрендинг
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Костя и Женя - создатели группы «Бумага» - после выпуска легендарного альбома решили создать новое музыкальное объединение «Дневные грузчики», для этого им нужно найти двух новых людей.

Они пригласили на кастинг $$$n$$$ человек. Кастинг продлится $$$q$$$ дней. В $$$i$$$-й из дней Костя и Женя хотят найти двух человек на отрезке с $$$l_i$$$ по $$$r_i$$$, которые больше всего подходят их объединению. Так как «Дневные грузчики» занимаются современным искусством,  музыкальные навыки им не важны и они смотрят лишь на внешние признаки: им хочется, чтобы разница роста двух людей была как можно меньше.

Помогите им, и для каждого дня укажите минимальную разницу роста людей с кастинга на данном отрезке!

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

В первой строке вам дано два целых числа $$$n$$$ и $$$q$$$ ($$$2 \leq n \leq 3 \cdot 10^5, 1 \leq q \leq 10^6$$$) — количество людей, которые пришли на кастинг, а также количество дней кастинга.

Во второй строке вам даны $$$n$$$ целых чисел $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — рост каждого из кандидатов.

Также гарантируется, что все $$$a_i$$$ различны.

В следующих $$$q$$$ строках даны по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i < r_i \leq n$$$) — отрезок людей в $$$i$$$-й день кастинга.

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

Выведите $$$q$$$ строк. В $$$i$$$-й строке должна быть минимальная разница роста между двумя кандидатами на отрезке в $$$i$$$-й день кастинга.

Примеры
Входные данные
3 3
1 3 2
1 2
2 3
1 3
Выходные данные
2
1
1
Входные данные
5 3
4 1 5 3 2
1 2
3 4
2 4
Выходные данные
3
2
2
Входные данные
7 4
2 6 1 7 3 5 4
4 6
1 2
3 6
1 3
Выходные данные
2
4
2
1
Примечание

В первом примере минимальная разность на отрезке $$$[1, 2]$$$ составляет $$$2$$$, на отрезке $$$[2, 3]$$$ — $$$1$$$, на отрезке $$$[1, 3]$$$ также $$$1$$$.

В третьем примере минимальную разность на отрезке $$$[4, 6]$$$ составляют числа $$$3$$$ и $$$5$$$ ($$$5 - 3 = 2$$$). На отрезке $$$[1, 2]$$$ минимальную разность имеют числа $$$2$$$ и $$$6$$$ ($$$6 - 2 = 4$$$). На отрезке $$$[3, 6]$$$ минимальную разность имеют числа $$$1$$$ и $$$3$$$ ($$$3 - 1 = 2$$$). На отрезке $$$[1, 3]$$$ минимальную разность образуют числа $$$1$$$ и $$$2$$$ ($$$2 - 1 = 1$$$).