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;
const int inf = 1e9 + 79, logn = 20, maxn = 3e5 + 79;
vector<vector<int> > rmql(logn, vector<int>(maxn, inf)),
    rmqr(logn, vector<int>(maxn, -inf));
vector<vector<int> > l(logn, vector<int>(maxn, inf)),
    r(logn, vector<int>(maxn, -inf));
vector<int> logs(maxn, 0);
int mini(int i1, int i2) { return (l[0][i1] < l[0][i2] ? i1 : i2); }
int maxi(int i1, int i2) { return (r[0][i1] > r[0][i2] ? i1 : i2); }
void query(int l, int r, int& ansl, int& ansr) {
  int s = logs[r - l + 1];
  ansl = mini(rmql[s][l], rmql[s][r - (1 << s) + 1]);
  ansr = maxi(rmqr[s][l], rmqr[s][r - (1 << s) + 1]);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  if (n == 1) {
    cout << "0\n";
    return 0;
  }
  vector<int> d(3 * n);
  for (int i = 0; i < n; i++) cin >> d[i], d[i + n] = d[i + 2 * n] = d[i];
  for (int i = 0; i < 3 * n; i++) {
    l[0][i] = max(0, i - d[i]);
    r[0][i] = min(3 * n - 1, i + d[i]);
    if (i > 1) logs[i] = logs[i / 2] + 1;
  }
  for (int i = 0; i < 3 * n; i++) rmql[0][i] = rmqr[0][i] = i;
  for (int i = 1; i < logn; i++) {
    for (int j = 0; j + (1 << i) <= 3 * n; j++) {
      rmql[i][j] = mini(rmql[i - 1][j], rmql[i - 1][j + (1 << (i - 1))]);
      rmqr[i][j] = maxi(rmqr[i - 1][j], rmqr[i - 1][j + (1 << (i - 1))]);
    }
  }
  for (int i = 1; i < logn; i++) {
    for (int j = 0; j < 3 * n; j++) {
      int nwl, nwr;
      query(l[i - 1][j], r[i - 1][j], nwl, nwr);
      l[i][j] = min(l[i - 1][nwl], l[i - 1][nwr]);
      r[i][j] = max(r[i - 1][nwl], r[i - 1][nwr]);
    }
  }
  for (int i = 0; i < n; i++) {
    int ans = 1, myl = n + i, myr = n + i;
    for (int j = logn - 1; j >= 0; j--) {
      int nwl = min(l[j][myl], l[j][myr]), nwr = max(r[j][myl], r[j][myr]);
      if (nwr - nwl + 1 < n) {
        int tmpl = l[j][myl], tmpr = r[j][myr];
        query(tmpl, tmpr, myl, myr);
        ans += (1 << j);
      }
    }
    cout << ans << " \n"[i == n - 1];
  }
  return 0;
}
