Костя и Женя — создатели группы «Бумага» — после выпуска легендарного альбома решили создать новое музыкальное объединение «дневные грузчики», для этого им нужно найти двух новых людей.
Они пригласили на кастинг $$$n$$$ человек. Кастинг продлится $$$q$$$ дней. В $$$i$$$-й из дней Костя и Женя хотят найти двух человек на отрезке с $$$l_i$$$ по $$$r_i$$$, которые больше всего подходят их объединению. Так как «дневные грузчики» занимаются современным искусством, музыкальные навыки им не важны, и они смотрят лишь на внешние признаки: им хочется, чтобы разница роста двух людей была как можно меньше.
Помогите им, и для каждого дня укажите минимальную разницу роста людей с кастинга на данном отрезке!
В первой строке вам дано два числа $$$n, q$$$ ($$$2 \leqslant n \leqslant 4 \cdot 10^5, 1 \leqslant q \leqslant 10^6$$$) — количество людей, которые пришли на кастинг, а также количество дней кастинга.
Во второй строке вам даны $$$n$$$ чисел $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \leqslant a_i \leqslant n$$$) — рост каждого из кандидатов.
Также гарантируется, что все $$$a_i$$$ различны.
В следующих $$$q$$$ строках даны по $$$2$$$ числа $$$l_i, r_i$$$ ($$$1 \leqslant l_i < r_i \leqslant n$$$) — отрезок людей для рассмотрения в $$$i$$$-й день кастинга.
Выведите $$$q$$$ строк. В $$$i$$$-й строке должна быть минимальная разница роста между двумя кандидатами на отрезке в $$$i$$$-й день кастинга.
3 31 3 21 22 31 3
2 1 1
5 34 1 5 3 21 23 42 4
3 2 2
7 42 6 1 7 3 5 44 61 23 61 3
2 4 2 1
В первом примере минимальная разность на отрезке $$$[1, 2]$$$ составляет $$$2$$$ ($$$3 - 1 = 2$$$), на отрезке $$$[2, 3]$$$ – $$$1$$$, на отрезке $$$[1, 3]$$$ также $$$1$$$.
В третьем примере минимальную разность на отрезке $$$[4, 6]$$$ составляют числа $$$3, 5$$$ ($$$5 - 3 = 2$$$). На отрезке $$$[1, 2]$$$ минимальную разность имеют числа $$$2, 6$$$ ($$$6 - 2 = 0$$$). На отрезке $$$[3, 6]$$$ минимальную разность имеют числа $$$1, 3$$$ ($$$3 - 1 = 2$$$). На отрезке $$$[1, 3]$$$ минимальную разность образуют числа $$$1, 2$$$ ($$$2 - 1 = 1$$$).
Тесты к этой задаче состоят из 10 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.
Доп. ограничения | |||||
Группа | Баллы | $$$n$$$ | $$$q$$$ | Необх. группы | Комментарий |
0 | 0 | – | – | – | Тесты из условия. |
1 | 12 | $$$n \le 50$$$ | $$$q \leqslant 50$$$ | 0 | |
2 | 11 | $$$n \leqslant 3000$$$ | $$$q \leqslant 3000$$$ | 0, 1 | |
3 | 14 | $$$n \leqslant 50\,000$$$ | $$$q \leqslant 50\,000$$$ | 0–2 | |
4 | 14 | $$$n \leqslant 100\,000$$$ | $$$q \leqslant 100\,000$$$ | – | Длины отрезков равны. |
5 | 11 | $$$n \leqslant 100\,000$$$ | $$$q \leqslant 100\,000$$$ | 0–4 | |
6 | 9 | $$$n \leqslant 200\,000$$$ | $$$q \leqslant 200\,000$$$ | 0–5 | |
7 | 9 | $$$n \leqslant 300\,000$$$ | $$$q \leqslant 300\,000$$$ | 0–6 | |
8 | 10 | – | $$$q \leqslant 400\,000$$$ | 0–8 | |
9 | 10 | – | – | 0–9 |