*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
# https://github.com/Tsuzat/fast-IO-for-python/blob/master/fast_IO/__init__.py


#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

# region fastio

BUFSIZE: int = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

import math,random,collections
from collections import deque
from math import floor,ceil,sqrt,gcd
from random import randint


if __name__ == "__main__":
    pass

# prime factorize
prime = []
primeset = set()

# https://www.geeksforgeeks.org/sieve-eratosthenes-0n-time-complexity/
def getPrimes(N):
    global prime
    global primeset

    isprime = [True for i in range(N+1)]
    isprime[0] = isprime[1] = False
    SPF = [None] * (N)

    for i in range(2, N):
        if isprime[i]:
            prime.append(i)
            SPF[i] = i

        j = 0
        while (j < len(prime) and
               i * prime[j] < N and
                   prime[j] <= SPF[i]):

            isprime[i * prime[j]] = False
            SPF[i * prime[j]] = prime[j]
            j += 1
    
    primeset = set(prime)

def getRidOf(n,p):
    while n % p == 0: n = n//p
    return n

def factors(n):
    ans = dict()
    if len(prime) < math.ceil(math.sqrt(n))+3:
        getPrimes(math.ceil(math.sqrt(n))+5)
    for i in prime:
        if i > math.ceil(math.sqrt(n))+3: break
        while n % i == 0:
            if i in ans: ans[i] += 1
            else: ans[i] = 1
            n = n // i
    if n > 1:
        if n in ans: ans[n] += 1
        else: ans[n] = 1
    
    return ans

def totient(n):
    totient = n
    for factor in factors(n):
        totient -= totient // factor
    return totient

# https://www.geeksforgeeks.org/square-free-number/
def squarefree(n):
    if n % 2 == 0:
        n = n / 2
    if n % 2 == 0:
        return False

    for i in range(3, int(sqrt(n) + 1)):
        if n % i == 0:
            n = n / i
        if n % i == 0:
            return False
    return True

# https://smsxgz.github.io/post/pe/counting_square_free_numbers/
mobiusList = []
def mobius(n):
    global mobiusList

    if n < len(mobiusList): return mobiusList[n]
    prime = [1] * (n + 1)
    mobiusList = [1] * (n + 1)

    for i in range(2, n + 1):
        if not prime[i]:
            continue
        mobiusList[i] = -1
        for j in range(2, n // i + 1):
            prime[i * j] = 0
            mobiusList[i * j] *= -1
        for j in range(1, n // (i * i) + 1):
            mobiusList[j * i * i] = 0
    return mobiusList

# https://smsxgz.github.io/post/pe/counting_square_free_numbers/
def count_squarefree(N):
    global mobius

    Imax = int(pow(N//4,1/3))
    D = int(sqrt(N / Imax))
    mobius(D)

    # compute S1
    s1 = 0
    for i in range(1, D + 1):
        s1 += mobiusList[i] * (N // (i * i))

    # compute M(d), d = 1, ..., D
    M_list = [0]
    M = 0
    for m in mobiusList[1:]:
        M += m
        M_list.append(M)

    # compute M(sqrt(n / i)), i = Imax - 1, ..., 1
    Mxi_list = []
    Mxi_sum = 0
    for i in range(Imax - 1, 0, -1):
        Mxi = 1
        xi = int(sqrt(N // i))

        sqd = int(sqrt(xi))
        # sqd < D <= xi
        for j in range(1, xi // (sqd + 1) + 1):
            Mxi -= (xi // j - xi // (j + 1)) * M_list[j]

        for j in range(2, sqd + 1):
            if xi // j <= D:
                Mxi -= M_list[xi // j]
            else:
                Mxi -= Mxi_list[Imax - j * j * i - 1]

        Mxi_list.append(Mxi)
        Mxi_sum += Mxi

    # compute S2
    s2 = Mxi_sum - (Imax - 1) * M_list[-1]
    return s1 + s2

def intArrToStr(a):
    return " ".join([str(x) for x in a])

def isPrime(n):
    prime_flag = 0
    
    if(n > 1):
        for i in range(2, int(sqrt(n)) + 1):
            if (n % i == 0):
                prime_flag = 1
                break
        return (prime_flag == 0)
    else:
        return False

from itertools import compress


def primes2(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
        sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]


def dsum(a):
    if type(a) == type(1): return a
    else: return sum([dsum(b) for b in a])

# Modify these functions for binary search
def binarySearchArrayGet(x): pass
def binarySearchArrayLength(): pass
def binarySearchCompare(x,y): pass

# Exact, Floor, Ceiling
def binarySearch(element, style="Exact"):
    l = 0
    r = binarySearchArrayLength()-1

    while l+1 < r:
        m = (l+r+randint(0,1))//2
        if binarySearchCompare(binarySearchArrayGet(m), element) <= 0:
            l = m
        if m != binarySearchArrayLength()-1 and binarySearchCompare(binarySearchArrayGet(m+1), element) > 0:
            r = m+1
    
    if style in ["Exact","exact","E","e",0.5]:
        if binarySearchCompare(binarySearchArrayGet(l), element) == 0: return l
        if binarySearchCompare(binarySearchArrayGet(r), element) == 0: return r

        return -1
    
    if style in ["Floor","floor","F","f",0]:
        if binarySearchCompare(binarySearchArrayGet(l), element) > 0: return -1
        if binarySearchCompare(binarySearchArrayGet(r), element) > 0: return l
        
        return r
        
    if style in ["Ceiling","ceiling","Ceil","ceil","C","c",1]:        
        if binarySearchCompare(binarySearchArrayGet(r), element) < 0: return -1
        if binarySearchCompare(binarySearchArrayGet(l), element) < 0: return r

        return l
    
    raise Exception("Binary search style invalid!")

def column(arr,col):
    a = []
    for i in arr:
        a.append(i[col])
    return a

def removeDuplicates(a):
    b = []
    for i in range(len(a))-1:
        if a[i] != a[i+1]: b.append(a[i])
    b.append(a[-1])
    return b

def intArrInput():
    *a, = map(int,input().split())
    return a

def digitStringToArr(s):
    return [int(x) for x in s]

def stringSeparatorToArr(s,sep):
    return [int(x) for x in s.split(sep)]

def spacedStringToArr(s):
    return stringSeparatorToArr(s," ")

# https://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform
def fwht(a) -> None:
    """In-place Fast Walsh–Hadamard Transform of array a."""
    h = 1
    while h < len(a):
        # perform FWHT
        for i in range(0, len(a), h * 2):
            for j in range(i, i + h):
                x = a[j]
                y = a[j + h]
                a[j] = x + y
                a[j + h] = x - y
        # normalize and increment
        h *= 2

def xorConvolution(c,d):
    # assuming a and b already have the same number of elements that is a power of 2
    a = c.copy()
    b = d.copy()
    fwht(a)
    fwht(b)
    
    hi = []
    for i in range(len(a)):
        hi.append(a[i]*b[i])
    fwht(hi)
    for j in range(len(hi)):
        hi[j] //= len(a)
    return hi

def mex(a):
    b = set(a)
    for i in range(len(a)+2):
        if i not in b: return i
    raise Exception("What")

def freqDict(a):
    ans = dict()
    for i in a:
        if i in ans: ans[i] += 1
        else: ans[i] = 1
    return ans

from random import getrandbits

RANDOM = getrandbits(32)

class Wrapper(int):
    def __init__(self, x):
        int.__init__(x)
    def __hash__(self):
        return super(Wrapper, self).__hash__() ^ RANDOM

def dictGet(x,d):
    if type(x) is int: x = str(x)
    return d[x]

def addTo(x,d):
    if type(x) is int: x = str(x)
    if x in d: d[x] += 1
    else: d[x] = 1

import random

RANDOMFORDICT = random.randrange((1 << 31) - 1)

class Dict(dict):
    def __setitem__(self, __k, __v):
        return super().__setitem__(__k ^ RANDOMFORDICT, __v)

    def __delitem__(self, __v):
        return super().__delitem__(__v ^ RANDOMFORDICT)

    def __getitem__(self, __k):
        return super().__getitem__(__k ^ RANDOMFORDICT)

    def __contains__(self, __o: object) -> bool:
        return super().__contains__(__o ^ RANDOMFORDICT)

# -----------------------------------------------------------------

def binarySearchArrayGet(x):
    return [1,2,3,5,6][x]

def binarySearchArrayLength():
    return 5

def binarySearchCompare(x,y):
    return x-y

generatePrimes = False
PRIMELIMIT = 10**5+12345

if generatePrimes:
    prime = primes2(PRIMELIMIT)
    primeset = set(prime)

# -----------------------------------------------------------------

import math

n = int(input())
a = intArrInput()
q = int(input())

precomp = [[]]

for i in range(1,int(math.sqrt(n))):
    stuff = [0 for i in range(n)]
    stuff[-1] = 1
    for j in range(n-2,-1,-1):
        lol = a[j] + j + i
        if lol >= n: stuff[j] = 1
        else: stuff[j] = stuff[lol] + 1
    precomp.append(stuff)

for i in range(n):
    x,y = intArrInput()
    x -= 1
    c = 0
    if y > math.sqrt(n)-3:
        while x < n:
            x += a[x] + y
            c += 1
    else:
        c = precomp[y][x]
    print(c)