Statement is not available in English language
F. Скучная задача
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
128 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан строго возрастающий массив $$$a$$$ длины $$$n$$$, состоящий из положительных целых чисел. Также вам дано $$$q$$$ запросов, $$$i$$$-й из которых определяется двумя целыми числами $$$l_i$$$, $$$r_i$$$ ($$$1 \leq l_i \lt r_i \leq n$$$). Ответ на $$$i$$$-й запрос — минимальное значение $$$a_c \bmod a_b$$$ (остаток от деления $$$a_c$$$ на $$$a_b$$$) по всем $$$l_i \leq b \lt c \leq r_i$$$.

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

В первой строке находится единственное целое число $$$n$$$ ($$$2 \leq n \leq 10^6$$$).

На второй строке находится $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^6$$$). Гарантируется, что $$$a_{i+1} \gt a_i$$$, то есть массив строго возрастает.

В третьей строке находится единственное целое число $$$q$$$ ($$$1 \leq q \leq 10^6$$$).

В следующих $$$q$$$ строках даны по два числа, в $$$i$$$-й из которых находятся целые числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \lt r_i \leq n$$$) — описание $$$i$$$-го запроса.

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

Выведите $$$q$$$ строк, в $$$i$$$-й ответ на $$$i$$$-й запрос.

Система оценки

Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Итоговый балл за каждую группу равняется максимальному баллу, полученному за эту группу тестов по всем отправленным посылкам.

|c|c|}

Подзадача

 Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
00Примеры из условия—полная проверка
112$$$n, q, a_i \leq 500$$$0первая ошибка
217$$$n, q, a_i \leq 3000$$$0–1первая ошибка
326$$$n, q, a_i \leq 2 \times 10^5$$$0–2первая ошибка
425$$$n, q, a_i \leq 625000$$$0–3первая ошибка
59$$$l_i = 0$$$—первая ошибка
611Без дополнительных ограничений0–5первая ошибка
Примеры
Входные данные
4
2 3 5 7
2
1 4
2 3
Выходные данные
1
2
Входные данные
8
3 8 10 11 21 23 25 30
7
1 8
1 7
7 8
2 7
3 8
3 6
1 6
Выходные данные
0
0
5
1
0
1
0
Примечание

Рассмотрим массив $$$a = [2, 3, 5, 7]$$$ ($$$n = 4$$$) и два запроса.

Запрос $$$1$$$: $$$l = 1$$$, $$$r = 4$$$. Разрешены все пары $$$(b, c)$$$, для которых $$$1 \le b \lt c \le 4$$$. Вычислим $$$a_c \bmod a_b$$$ для каждой пары:

  • $$$(b, c) = (1, 2)$$$: $$$a_2 \bmod a_1 = 3 \bmod 2 = 1$$$;
  • $$$(b, c) = (1, 3)$$$: $$$a_3 \bmod a_1 = 5 \bmod 2 = 1$$$;
  • $$$(b, c) = (1, 4)$$$: $$$a_4 \bmod a_1 = 7 \bmod 2 = 1$$$;
  • $$$(b, c) = (2, 3)$$$: $$$a_3 \bmod a_2 = 5 \bmod 3 = 2$$$;
  • $$$(b, c) = (2, 4)$$$: $$$a_4 \bmod a_2 = 7 \bmod 3 = 1$$$;
  • $$$(b, c) = (3, 4)$$$: $$$a_4 \bmod a_3 = 7 \bmod 5 = 2$$$.
Минимальное значение равно $$$1$$$, поэтому ответ на первый запрос равен $$$1$$$.

Запрос $$$2$$$: $$$l = 2$$$, $$$r = 3$$$. Здесь единственная допустимая пара $$$(b, c) = (2, 3)$$$: $$$a_3 \bmod a_2 = 5 \bmod 3 = 2$$$. Поэтому ответ на второй запрос равен $$$2$$$.