Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

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

(Время: 2 сек. Память: 16 Мб Сложность: 74%)

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

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

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

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

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

В третьей строке содержится число M (1 ≤ M ≤ 105) – количество запросов. В каждой из следующих M строк задаются параметры для вычисления Lk и Rk – пара целых чисел xk, yk. Lk в соответствующем запросе вычисляется по формуле Lk = (xk + ansk − 1) mod N , а Rk – по формуле Rk = (yk + ansk − 1) mod N , где ansi – ответ на i-ый запрос, при этом ans0 = 0.

Гарантируется, что Lk < Rk и 0 ≤ xk, yk < N (1 ≤ k ≤ M ).

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

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

Примеры

INPUT.TXTOUTPUT.TXT
16
1 10 2 5 -10 0
4
0 1
4 1
3 2
2 4
9
3
1
5
23
7 7 7
1
0 2
0

Пояснение

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


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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая командная олимпиада
 Вторая командная олимпиада
 Третья командная олимпиада
 Четвертая командная олимпиада
 Пятая командная олимпиада
 Шестая командная олимпиада
 Седьмая командная олимпиада
 A. Высота треугольника
 B. Болото
 C. ДНК-палиндром
 D. Сыграешь с Денисом?
 E. Акции
 F. Сказочная страна
 G. Hello world!
 H. Гонки

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru