F. Сувениры
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Артём поехал на море и хочет привести двум своим сокомандникам сувениры. На главной туристической улице города есть n магазинов. В i-м магазине Артём может купить один сувенир за ai рублей, покупать больше одного сувенира в одном магазине нельзя. Артём не хочет сеять зависть в своей команде, поэтому цена двух сувениров, которые он привезёт друзьям, должна отличаться как можно меньше.

Артём заходил на улицу с магазинчиками m раз. По неизвестной причине в его i-й визит работали только магазины с номерами с li по ri (бред? да, но вы сами когда-нибудь пытались придумать вразумительную легенду к задаче про запросы на отрезках?). Для каждого визита Артём хочет узнать минимальную возможную разность между ценой сувениров, которые он может купить в открытых магазинах.

Другими словами, для каждого раза, когда Артём заходил на улицу, найдите минимально возможное значение |as - at|, где li ≤ s, t ≤ ri, s ≠ t.

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

В первой строке входного файла содержится целое число n (2 ≤ n ≤ 105).

Во второй строке содержатся n целых чисел a1, ..., an (0 ≤ ai ≤ 109).

В третьей строке содержится целое число m — количество запросов (1 ≤ m ≤ 3·105).

Следующие m строк описывают запросы. i-я строка содержит два числа li, ri, обозначающих отрезок работающих в i-й день магазинов (1 ≤ li < ri ≤ n).

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

Для каждого запроса выведите в отдельной строке минимальную разницу между ценой сувениров.

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