Сказочная страна

Учёный-волшебник Квазислав находится на грани великого открытия. Остался последний эксперимент: Квазислав собирается открыть портал при помощи запуска аппарата, который он пока называет просто «Чудо-Машина». Помимо волшебной пыли и стержня плутония, для катализации процессов «Чудо-Машины» необходимы несколько плазмоидов.

Перед Квазиславом расположены в ряд N заряженных плазмоидов, пронумерованных последовательными целыми числами от 0 до N−1. i-ый из плазмоидов имеет заряд a_i. Квазислав должен взять некоторую группу плазмоидов, расположенных подряд. Для Квазислава важным параметром является хаотичность группы, определяемая как минимальный модуль разности между зарядами двух плазмоидов в этой группе.

Для того, чтобы подобрать оптимальные параметры эксперимента, Квазислав хочет проверить несколько групп плазмоидов, каждая группа характеризуется номерами её самого левого плазмоида L_k и самого правого плазмоида R_k. К сожалению, L_k и R_k вычисляются не так просто, так что он просит Вас о помощи. Если Вы ответите на его запросы достаточно быстро, то возможно, Вы станете первым человеком, не только вошедшим в открытый портал, но и вышедшим из него.

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

Первая строка входного файла INPUT.TXT содержит целое число N (2 ≤ N ≤ 10⁴) – количество плазмоидов. Во второй строке содержатся N целых чисел a_i, разделённых пробелами – заряды плазмоидов (−10⁹ ≤ a_i ≤ 10⁹).

В третьей строке содержится число M (1 ≤ M ≤ 10⁵) – количество запросов. В каждой из следующих M строк задаются параметры для вычисления L_k и R_k – пара целых чисел x_k, y_k. L_k в соответствующем запросе вычисляется по формуле L_k = (x_k + ans_k−1) mod N , а R_k – по формуле R_k = (y_k + ans_k−1) mod N , где ans_i – ответ на i-ый запрос, при этом ans₀ = 0.

Гарантируется, что L_k < R_k и 0 ≤ x_k, y_k < N (1 ≤ k ≤ M ).

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

В выходной файл OUTPUT.TXT выведите ответ на каждый запрос в отдельной строке.

Примеры

Пояснение

Границы запросов в первом примере: [0, 1], [1, 4], [0, 5], [3, 5].

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!