Задача №114939. Ребрендинг
Костя и Женя — создатели группы «Бумага» — после выпуска легендарного альбома решили создать новое музыкальное объединение «дневные грузчики», для этого им нужно найти двух новых людей.
Они пригласили на кастинг \(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\)-й день кастинга.
В первом примере минимальная разность на отрезке \([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 | |
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