*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*<sub class="lower-index">*p*</sub> + *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*<sub class="lower-index">*i*</sub> ≤ *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*).
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.
3
1 1 1
3
1 1
2 1
3 1
2
1
1
10
3 5 4 3 7 10 6 7 2 3
10
4 5
2 10
4 6
9 9
9 2
5 1
6 4
1 1
5 6
6 4
1
1
1
1
1
1
1
2
1
1
50
6 2 5 6 10 2 5 8 9 2 9 5 10 4 3 6 10 6 1 1 3 7 2 1 7 8 5 9 6 2 7 6 1 7 2 10 10 2 4 2 8 4 3 10 7 1 7 8 6 3
50
23 8
12 8
3 3
46 3
21 6
7 4
26 4
12 1
25 4
18 7
29 8
27 5
47 1
50 2
46 7
13 6
44 8
12 2
18 3
35 10
38 1
7 10
4 2
22 8
36 3
25 2
47 3
33 5
10 5
12 9
7 4
26 4
19 4
3 8
12 3
35 8
31 4
25 5
3 5
46 10
37 6
8 9
20 5
36 1
41 9
6 7
40 5
24 4
41 10
14 8
3
4
6
2
4
5
3
8
3
3
2
2
1
1
1
3
1
6
5
2
3
3
7
2
2
4
1
3
4
3
5
3
5
5
6
2
3
2
4
1
1
3
4
2
1
5
2
4
1
3
50
49 21 50 31 3 19 10 40 20 5 47 12 12 30 5 4 5 2 11 23 5 39 3 30 19 3 23 40 4 14 39 50 45 14 33 37 1 15 43 30 45 23 32 3 9 17 9 5 14 12
50
36 29
44 24
38 22
30 43
15 19
39 2
13 8
29 50
37 18
32 19
42 39
20 41
14 11
4 25
14 35
17 23
1 29
3 19
8 6
26 31
9 46
36 31
21 49
17 38
47 27
5 21
42 22
36 34
50 27
11 45
26 41
1 16
21 39
18 43
21 37
12 16
22 32
7 18
10 14
43 37
18 50
21 32
27 32
48 16
5 6
5 11
5 6
39 29
40 13
14 6
1
1
1
1
2
1
2
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
2
1
2
3
1
1
1
1
1
3
3
3
1
1
2
from collections import defaultdict, deque, Counter
import sys
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce, lru_cache
from bisect import bisect_left, bisect_right

def input():
    return sys.stdin.readline().rstrip()
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getListGraph():
    return list(map(lambda x:int(x) - 1, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

mod = 10 ** 9 + 7
MOD = 998244353
# sys.setrecursionlimit(10000000)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
inf = float('inf')
eps = 10 ** (-12)
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

#############
# Main Code #
#############

N = getN()
A = getList()
lim = int(math.sqrt(N))
# kの大きさで分類
Q = getN()
que = []
want = set()
for i in range(Q):
    p, k = getNM()
    p -= 1
    if k <= lim:
        want.add((p, k))
    que.append([p, k])

L = [0] * (N + 1)
D = defaultdict(int)
# k以下は解法2でやる
# O(N√N)でk<limの全てに対応できる
for k in range(1, lim):
    # 後ろからdp
    for j in range(N - 1, -1, -1):
        L[j] = L[min(N, j + A[j] + k)] + 1
        if (j, k) in want:
            D[(j, k)] = L[j]

for p, k in que:
    if k < lim:
        print(D[(p, k)])
    else:
        # 解法1　愚直
        ans = 0
        while p < N:
            ans += 1
            p = p + A[p] + k
        print(ans)