Вам дан строго возрастающий массив $$$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|} Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Примеры из условия | — | полная проверка |
| 1 | 12 | $$$n, q, a_i \leq 500$$$ | 0 | первая ошибка |
| 2 | 17 | $$$n, q, a_i \leq 3000$$$ | 0–1 | первая ошибка |
| 3 | 26 | $$$n, q, a_i \leq 2 \times 10^5$$$ | 0–2 | первая ошибка |
| 4 | 25 | $$$n, q, a_i \leq 625000$$$ | 0–3 | первая ошибка |
| 5 | 9 | $$$l_i = 0$$$ | — | первая ошибка |
| 6 | 11 | Без дополнительных ограничений | 0–5 | первая ошибка |
42 3 5 721 42 3
1 2
83 8 10 11 21 23 25 3071 81 77 82 73 83 61 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$$$ для каждой пары:
Запрос $$$2$$$: $$$l = 2$$$, $$$r = 3$$$. Здесь единственная допустимая пара $$$(b, c) = (2, 3)$$$: $$$a_3 \bmod a_2 = 5 \bmod 3 = 2$$$. Поэтому ответ на второй запрос равен $$$2$$$.
