a 是一个由 n 个正整数组成的数组,所有正整数都不大于 n。
您必须处理对此数组的 q 个查询。每个查询由两个数字 p 和 k 表示。每个查询中执行多个操作;每个操作将 p 更改为 p + ap + k。应用这些操作直到 p 变得大于 n。查询的答案是执行的操作数。
输入
第一行包含一个整数 n (1 ≤ n ≤ 100000)。
第二行包含 n 个整数 — a 的元素(对于从 1 到 n 的每个 i,1 ≤ ai ≤ n)。
第三行包含一个整数 q (1 ≤ q ≤ 100000)。
接下来是 q 行。每行包含相应查询的 p 和 k 值 (1 ≤ p, k ≤ n)。
输出
打印 q 个整数,第 i 个整数必须等于第 i 个查询的答案。
示例
输入 #1
3 1 1 1 3 1 1 2 1 3 1
输出 #1
2 1 1
注意
考虑第一个例子:
在第一次操作后的第一次查询中 p = 3,在第二次操作后 p = 5。
在接下来的两个查询中,第一个操作后 p 大于 n。