CF797E.Array Queries

a is an array of n positive integers, all of which are not greater than n.

You have to process q queries to this array. Each query is represented by two numbers p and k. Several operations are performed in each query; each operation changes p to p + a__p + k. There operations are applied until p becomes greater than n. The answer to the query is the number of performed operations.

数组 $a$ 包含 $n$ 个正整数，且每个元素都不超过 $n$。

你需要处理该数组上的 $q$ 个查询。每个查询由两个数 $p$ 和 $k$ 表示。对每个查询执行若干次操作：每次操作将 $p$ 更新为 $p + a_p + k$。重复该操作，直到 $p$ 大于 $n$ 为止。该查询的答案即为所执行的操作次数。

The first line contains one integer n (1 ≤ n ≤ 100000).

The second line contains n integers — elements of a (1 ≤ a__i ≤ n for each i from 1 to n).

The third line containts one integer q (1 ≤ q ≤ 100000).

Then q lines follow. Each line contains the values of p and k for corresponding query (1 ≤ p, k ≤ n).

第一行包含一个整数 $n$（$1 \leq n \leq 100000$）。

第二行包含 $n$ 个整数——数组 $a$ 的元素（对每个 $i$ 从 $1$ 到 $n$，满足 $1 \leq a_i \leq n$）。

第三行包含一个整数 $q$（$1 \leq q \leq 100000$）。

接下来是 $q$ 行。每行包含对应查询的 $p$ 和 $k$ 的值（$1 \leq p,\,k \leq n$）。

Print q integers, _i_th integer must be equal to the answer to _i_th query.

输出 q 个整数，其中第 i 个整数必须等于第 i 个查询的答案。

Consider first example:

In first query after first operation p = 3, after second operation p = 5.

In next two queries p is greater than n after the first operation.

先考虑第一个例子：

在第一次查询中，第一次操作后 $p = 3$，第二次操作后 $p = 5$。

在接下来的两次查询中，第一次操作后 $p$ 已大于 $n$。