E. Запросы на массиве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив a из n элементов, все элементы — натуральные числа, не превышающие n.

Необходимо обработать q запросов к этому массиву. Каждый запрос задаётся двумя числами p и k. Запрос состоит из нескольких операций, каждая операция заменяет число p числом p + ap + k. Эти операции проводятся, пока p не станет больше, чем n. Для каждого запроса необходимо выяснить количество таких операций.

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

В первой строке входного файла задано единственное число n (1 ≤ n ≤ 100000).

Во второй строке задано n целых чисел — массив a (1 ≤ ai ≤ n для всех i от 1 до n).

В третьей строке задано число q — количество запросов (1 ≤ q ≤ 100000).

В следующих q строках задано по два числа p и k (1 ≤ p, k ≤ n) — описание очередного запроса.

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

Выведите q чисел, i-е из них должно быть равно ответу на запрос под номером i.

Пример
Входные данные
3
1 1 1
3
1 1
2 1
3 1
Выходные данные
2
1
1
Примечание

Разберём пример из условия:

В первом запросе после первой операции p = 3, после второй p = 5.

Во втором и третьем запросах p становится больше n уже после первой операции.