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 N = 3e5 + 10, lg = 20, mod = 1e9 + 7;
int n, m, q;
int ds[N], lg2[N], power2[lg], tmp[2][N], l[lg][N], r[lg][N], rmq[2][lg][N];
void preprocess() {
  lg2[1] = 0, power2[0] = 1;
  for (int i = 1; i < lg; i++) power2[i] = power2[i - 1] * 2;
  for (int i = 2; i < N; i++) lg2[i] = lg2[i >> 1] + 1;
}
int maxr(int x, int y, bool b) {
  if (tmp[b][x] < tmp[b][y]) return y;
  return x;
}
void Build(bool b) {
  for (int i = 1; i <= 3 * n; i++) {
    rmq[b][0][i] = i;
    if (b)
      tmp[b][i] = r[0][i];
    else
      tmp[b][i] = -l[0][i];
  }
  for (int i = 1; i < lg; i++) {
    for (int j = 1; j <= 3 * n; j++) {
      if (j + power2[i - 1] <= 3 * n)
        rmq[b][i][j] =
            maxr(rmq[b][i - 1][j], rmq[b][i - 1][j + power2[i - 1]], b);
      else
        rmq[b][i][j] = rmq[b][i - 1][j];
    }
  }
}
int maxar(int l, int r, int b) {
  int curlog = lg2[r - l + 1];
  return maxr(rmq[b][curlog][l], rmq[b][curlog][r - power2[curlog] + 1], b);
}
int main() {
  preprocess();
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> ds[i];
    ds[i + n + n] = ds[i + n] = ds[i];
  }
  if (n == 1) return cout << 0, 0;
  for (int i = 1; i <= 3 * n; i++) {
    l[0][i] = max(1, i - ds[i]);
    r[0][i] = min(3 * n, i + ds[i]);
  }
  Build(0);
  Build(1);
  for (int i = 1; i < lg; i++) {
    for (int j = 1; j <= 3 * n; j++) {
      int lp = maxar(l[i - 1][j], r[i - 1][j], 0);
      int rp = maxar(l[i - 1][j], r[i - 1][j], 1);
      l[i][j] = min(l[i - 1][lp], l[i - 1][rp]);
      r[i][j] = max(r[i - 1][lp], r[i - 1][rp]);
    }
  }
  for (int i = n + 1; i <= 2 * n; i++) {
    int ans = 1, u = i, v = i;
    for (int j = lg - 1; j >= 0; j--) {
      if (max(r[j][u], r[j][v]) - min(l[j][u], l[j][v]) < n - 1) {
        int lp = maxar(l[j][u], r[j][v], 0);
        int rp = maxar(l[j][u], r[j][v], 1);
        u = lp, v = rp, ans += power2[j];
      }
    }
    cout << ans << " ";
  }
}
