Артём поехал на море и хочет привести двум своим сокомандникам сувениры. На главной туристической улице города есть 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
Название |
---|