← 返回题目列表

Codeforces · 797/E

E. 数组查询

中文机器翻译题面 查看原题

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。