#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
class Scanner {
  char cht;
  bool ifNegative;
  char stringBuf[10000];
  char nc() {
    static char buf[524288];
    static char *p1 = buf + 524288, *pend = buf + 524288;
    if (p1 == pend) {
      p1 = buf;
      pend = buf + fread(buf, 1, 524288, stdin);
      if (pend == p1) return ' ';
    }
    if (*p1 == '-') {
      ifNegative = true;
      p1++;
      return nc();
    }
    return *p1++;
  }
  inline bool blank(char ch) {
    return ch == '\r' || ch == '\n' || ch == ' ' || ch == '\t';
  }

 public:
  Scanner operator>>(int &x) {
    ifNegative = false;
    while (blank(cht = nc()))
      ;
    for (x = cht - '0'; (cht = nc()) >= '0' && cht <= '9';
         x = x * 10 + cht - '0')
      ;
    if (ifNegative) x *= -1;
    return *this;
  }
  Scanner operator>>(long long int &x) {
    ifNegative = false;
    while (blank(cht = nc()))
      ;
    for (x = cht - '0'; (cht = nc()) >= '0' && cht <= '9';
         x = x * 10 + cht - '0')
      ;
    if (ifNegative) x *= -1;
    return *this;
  }
  Scanner operator>>(string &str) {
    int p = 0;
    while (blank(cht = nc()))
      ;
    for (stringBuf[p++] = cht; !blank(cht = nc()); stringBuf[p++] = cht)
      ;
    stringBuf[p] = '\0';
    str = stringBuf;
    return *this;
  }
  Scanner operator>>(char str[]) {
    int p = 0;
    while (blank(cht = nc()))
      ;
    for (str[p++] = cht; !blank(cht = nc()); str[p++] = cht)
      ;
    str[p] = '\0';
    return *this;
  }
  template <typename F>
  inline Scanner operator>>(F &f) {
    cin >> f;
    return *this;
  }
};
class Printer {
  int num;
  char chr[21];

 public:
  Printer operator<<(int x) {
    if (x == 0) {
      putchar('0');
      return *this;
    }
    if (x < 0) {
      x *= -1;
      putchar('-');
    }
    num = 0;
    while (x) {
      chr[++num] = (x % 10) + 48;
      x /= 10;
    }
    while (num) putchar(chr[num--]);
    return *this;
  }
  Printer operator<<(long long int x) {
    if (x == 0) {
      putchar('0');
      return *this;
    }
    if (x < 0) {
      x *= -1;
      putchar('-');
    }
    num = 0;
    while (x) {
      chr[++num] = (x % 10) + 48;
      x /= 10;
    }
    while (num) putchar(chr[num--]);
    return *this;
  }
  inline Printer operator<<(char x) {
    putchar(x);
    return *this;
  }
  Printer operator<<(const char str[]) {
    int p = 0;
    while (str[p] != '\0') {
      putchar(str[p++]);
    }
    return *this;
  }
  inline Printer operator<<(string &x) {
    for (string::iterator i = x.begin(); i < x.end(); i++) putchar(*i);
    return *this;
  }
  template <typename F>
  inline Printer operator<<(F &f) {
    cout << f;
    return *this;
  }
};
Scanner qin;
Printer qout;
}  // namespace FastIO
using namespace FastIO;
const int MAXN = 100005;
const int MAXM = 355;
const int INF = 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double PI = 3.141593;
const double E = 2.718282;
const double PHI = 1.618034;
int n, q, p, k;
int a[MAXN];
int dp[MAXN][MAXM];
int main() {
  qin >> n;
  for (register long long i = 1; i <= n; i++) qin >> a[i];
  qin >> q;
  for (register long long i = n; i >= 1; i--)
    for (register long long j = 1; j <= 349; j++) {
      if (i + a[i] + j > n)
        dp[i][j] = 1;
      else
        dp[i][j] = dp[i + a[i] + j][j] + 1;
    }
  for (register long long j = 1; j <= q; j++) {
    qin >> p >> k;
    if (k < 350)
      qout << dp[p][k] << '\n';
    else {
      int cnt = 1;
      while ((p = p + a[p] + k) <= n) cnt++;
      qout << cnt << '\n';
    }
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 + ap + k. There operations are applied until p becomes greater than n. The answer to the query is the number of performed operations.

Input

The first line contains one integer n (1 ≤ n ≤ 100000).

The second line contains n integers — elements of a (1 ≤ ai ≤ 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).

Output

Print q integers, ith integer must be equal to the answer to ith query.

Example

Input

3
1 1 1
3
1 1
2 1
3 1


Output

2
1
1

Note

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
class Scanner {
  char cht;
  bool ifNegative;
  char stringBuf[10000];
  char nc() {
    static char buf[524288];
    static char *p1 = buf + 524288, *pend = buf + 524288;
    if (p1 == pend) {
      p1 = buf;
      pend = buf + fread(buf, 1, 524288, stdin);
      if (pend == p1) return ' ';
    }
    if (*p1 == '-') {
      ifNegative = true;
      p1++;
      return nc();
    }
    return *p1++;
  }
  inline bool blank(char ch) {
    return ch == '\r' || ch == '\n' || ch == ' ' || ch == '\t';
  }

 public:
  Scanner operator>>(int &x) {
    ifNegative = false;
    while (blank(cht = nc()))
      ;
    for (x = cht - '0'; (cht = nc()) >= '0' && cht <= '9';
         x = x * 10 + cht - '0')
      ;
    if (ifNegative) x *= -1;
    return *this;
  }
  Scanner operator>>(long long int &x) {
    ifNegative = false;
    while (blank(cht = nc()))
      ;
    for (x = cht - '0'; (cht = nc()) >= '0' && cht <= '9';
         x = x * 10 + cht - '0')
      ;
    if (ifNegative) x *= -1;
    return *this;
  }
  Scanner operator>>(string &str) {
    int p = 0;
    while (blank(cht = nc()))
      ;
    for (stringBuf[p++] = cht; !blank(cht = nc()); stringBuf[p++] = cht)
      ;
    stringBuf[p] = '\0';
    str = stringBuf;
    return *this;
  }
  Scanner operator>>(char str[]) {
    int p = 0;
    while (blank(cht = nc()))
      ;
    for (str[p++] = cht; !blank(cht = nc()); str[p++] = cht)
      ;
    str[p] = '\0';
    return *this;
  }
  template <typename F>
  inline Scanner operator>>(F &f) {
    cin >> f;
    return *this;
  }
};
class Printer {
  int num;
  char chr[21];

 public:
  Printer operator<<(int x) {
    if (x == 0) {
      putchar('0');
      return *this;
    }
    if (x < 0) {
      x *= -1;
      putchar('-');
    }
    num = 0;
    while (x) {
      chr[++num] = (x % 10) + 48;
      x /= 10;
    }
    while (num) putchar(chr[num--]);
    return *this;
  }
  Printer operator<<(long long int x) {
    if (x == 0) {
      putchar('0');
      return *this;
    }
    if (x < 0) {
      x *= -1;
      putchar('-');
    }
    num = 0;
    while (x) {
      chr[++num] = (x % 10) + 48;
      x /= 10;
    }
    while (num) putchar(chr[num--]);
    return *this;
  }
  inline Printer operator<<(char x) {
    putchar(x);
    return *this;
  }
  Printer operator<<(const char str[]) {
    int p = 0;
    while (str[p] != '\0') {
      putchar(str[p++]);
    }
    return *this;
  }
  inline Printer operator<<(string &x) {
    for (string::iterator i = x.begin(); i < x.end(); i++) putchar(*i);
    return *this;
  }
  template <typename F>
  inline Printer operator<<(F &f) {
    cout << f;
    return *this;
  }
};
Scanner qin;
Printer qout;
}  // namespace FastIO
using namespace FastIO;
const int MAXN = 100005;
const int MAXM = 355;
const int INF = 0x3f3f3f3f;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double PI = 3.141593;
const double E = 2.718282;
const double PHI = 1.618034;
int n, q, p, k;
int a[MAXN];
int dp[MAXN][MAXM];
int main() {
  qin >> n;
  for (register long long i = 1; i <= n; i++) qin >> a[i];
  qin >> q;
  for (register long long i = n; i >= 1; i--)
    for (register long long j = 1; j <= 349; j++) {
      if (i + a[i] + j > n)
        dp[i][j] = 1;
      else
        dp[i][j] = dp[i + a[i] + j][j] + 1;
    }
  for (register long long j = 1; j <= q; j++) {
    qin >> p >> k;
    if (k < 350)
      qout << dp[p][k] << '\n';
    else {
      int cnt = 1;
      while ((p = p + a[p] + k) <= n) cnt++;
      qout << cnt << '\n';
    }
  }
  return 0;
}

```