CF797E.Array Queries

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

$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.

输入格式

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)$ .

输出格式

Print $q$ integers, $i$ th integer must be equal to the answer to $i$ th query.

输入输出样例

输入#1
```
3
1 1 1
3
1 1
2 1
3 1
```
输出#1
```
2
1
1
```

说明/提示

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.

首页