Костя и Женя - создатели группы «Бумага» - после выпуска легендарного альбома решили создать новое музыкальное объединение «Дневные грузчики», для этого им нужно найти двух новых людей.
Они пригласили на кастинг \(n\) человек. Кастинг продлится \(q\) дней. В \(i\)-й из дней Костя и Женя хотят найти двух человек на отрезке с \(l_i\) по \(r_i\), которые больше всего подходят их объединению. Так как «Дневные грузчики» занимаются современным искусством, музыкальные навыки им не важны и они смотрят лишь на внешние признаки: им хочется, чтобы разница роста двух людей была как можно меньше.
Помогите им, и для каждого дня укажите минимальную разницу роста людей с кастинга на данном отрезке!
Выходные данные
Выведите \(q\) строк. В \(i\)-й строке должна быть минимальная разница роста между двумя кандидатами на отрезке в \(i\)-й день кастинга.
Примечание
В первом примере минимальная разность на отрезке \([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\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 3 2
1 2
2 3
1 3
|
2
1
1
|
|
2
|
5 3
4 1 5 3 2
1 2
3 4
2 4
|
3
2
2
|
|
3
|
7 4
2 6 1 7 3 5 4
4 6
1 2
3 6
1 3
|
2
4
2
1
|