There are n parrots standing in a circle. Each parrot has a certain level of respect among other parrots, namely r_i. When a parrot with respect level x starts chattering, x neighbours to the right and to the left of it start repeating the same words in 1 second. Their neighbours then start repeating as well, and so on, until all the birds begin to chatter.

You are given the respect levels of all parrots. For each parrot answer a question: if this certain parrot starts chattering, how many seconds will pass until all other birds will start repeating it?

Input

In the first line of input there is a single integer n, the number of parrots (1 ≤ n ≤ 10^5).

In the next line of input there are n integers r_1, ..., r_n, the respect levels of parrots in order they stand in the circle (1 ≤ r_i ≤ n).

Output

Print n integers. i-th of them should equal the number of seconds that is needed for all parrots to start chattering if the i-th parrot is the first to start.

Examples

Input


4
1 1 4 1


Output


2 2 1 2 


Input


8
1 2 2 1 5 1 3 1


Output


3 3 2 2 1 2 2 3 
#include <bits/stdc++.h>
using namespace std;
vector<int> l, r, x;
vector<vector<int> > jl, jr;
int largmin(int i, int j) {
  if (l[i] < l[j]) return i;
  return j;
}
int rargmax(int i, int j) {
  if (r[i] > r[j]) return i;
  return j;
}
int lmin(int a, int b) {
  int z = 0;
  while ((1 << (z + 1)) <= b - a + 1) z += 1;
  return largmin(jl[z][b], jl[z][a - 1 + (1 << z)]);
}
int rmax(int a, int b) {
  int z = 0;
  while ((1 << (z + 1)) <= b - a + 1) z += 1;
  return rargmax(jr[z][a], jr[z][b + 1 - (1 << z)]);
}
int main() {
  int n;
  cin >> n;
  x.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i];
  }
  int N = 3 * n;
  l.resize(N);
  r.resize(N);
  for (int i = 0; i < N; i++) {
    l[i] = max(i - x[i % n], 0);
    r[i] = min(i + x[i % n], N - 1);
  }
  const int MAXJ = 20;
  jl.resize(MAXJ, vector<int>(N));
  jr.resize(MAXJ, vector<int>(N));
  for (int j = 0; j < MAXJ; j++) {
    for (int i = 0; i < N; i++) {
      if (j == 0) {
        jl[j][i] = jr[j][i] = i;
      } else {
        jl[j][i] = largmin(jl[j - 1][i], jl[j - 1][max(i - (1 << (j - 1)), 0)]);
        jr[j][i] =
            rargmax(jr[j - 1][i], jr[j - 1][min(i + (1 << (j - 1)), N - 1)]);
      }
    }
  }
  vector<vector<int> > lexpo(MAXJ, vector<int>(N));
  vector<vector<int> > rexpo(MAXJ, vector<int>(N));
  for (int j = 0; j < MAXJ; j++) {
    for (int i = 0; i < N; i++) {
      if (j == 0) {
        lexpo[j][i] = lmin(l[i], i);
        rexpo[j][i] = rmax(i, r[i]);
      } else {
        lexpo[j][i] = lexpo[j - 1][lexpo[j - 1][i]];
        rexpo[j][i] = rexpo[j - 1][rexpo[j - 1][i]];
      }
    }
  }
  vector<int> ans(n);
  for (int i = n; i < 2 * n; i++) {
    int curl = i;
    int curr = i;
    int nsteps = 0;
    while (1) {
      if (curr - curl + 1 >= n) break;
      for (int j = MAXJ - 1; j >= 0; j--) {
        int newl = lmin(curl, curr);
        int newr = rmax(curl, curr);
        int xl = lexpo[j][newl];
        int xr = rexpo[j][newr];
        if (r[rmax(xl, curl)] > curr) {
          continue;
        }
        if (l[lmin(curr, xr)] < curl) {
          continue;
        }
        if (r[xr] - l[xl] + 1 >= n) continue;
        curl = l[xl];
        curr = r[xr];
        nsteps += 1 + (1 << j);
      }
      if (curr - curl + 1 >= n) break;
      int newl = lmin(curl, curr);
      int newr = rmax(curl, curr);
      curl = l[newl];
      curr = r[newr];
      nsteps++;
    }
    ans[i - n] = nsteps;
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
  cout << '\n';
}
