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 = 1e5 + 2;
int n, a[N], c[N], L[18][N], R[18][N], curk, p = 1;
int t[2][18][N * 4];
void build(int v = 1, int tl = 1, int tr = n) {
  if (tl == tr) {
    t[0][curk][v] = L[curk][tl];
    t[1][curk][v] = R[curk][tl];
  } else {
    int tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build((v << 1) | 1, tm + 1, tr);
    t[0][curk][v] = min(t[0][curk][v << 1], t[0][curk][(v << 1) | 1]);
    t[1][curk][v] = max(t[1][curk][v << 1], t[1][curk][(v << 1) | 1]);
  }
}
int get(int k, int l, int r, int type, int v = 1, int tl = 1, int tr = n) {
  if (l > tr || tl > r) {
    if (type == 1)
      return -1e9;
    else
      return 1e9;
  }
  if (l <= tl && tr <= r) {
    return t[type][k][v];
  }
  int tm = (tl + tr) >> 1;
  if (!type)
    return min(get(k, l, r, type, v << 1, tl, tm),
               get(k, l, r, type, (v << 1) | 1, tm + 1, tr));
  else
    return max(get(k, l, r, type, v << 1, tl, tm),
               get(k, l, r, type, (v << 1) | 1, tm + 1, tr));
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
  }
  for (int i = 1; i <= n; i++) {
    c[i] = a[p];
    p++;
    if (p > n) p = 1;
    L[0][i] = i - c[i];
    R[0][i] = i + c[i];
  }
  build();
  for (int k = 1; k <= 17; k++) {
    for (int j = 1; j <= n; j++) {
      L[k][j] = get(curk, max(1, L[curk][j]), min(n, R[curk][j]), 0);
      R[k][j] = get(curk, max(1, L[curk][j]), min(n, R[curk][j]), 1);
      if (L[curk][j] < 1) {
        int lo = max(n - abs(L[curk][j]), 1), hi = n;
        int now = get(curk, lo, hi, 0);
        L[k][j] = min(L[k][j], -(n - now));
      }
      if (R[curk][j] > n) {
        int lo = 1, hi = min(n, R[curk][j] - n);
        int now = get(curk, lo, hi, 1);
        R[k][j] = max(R[k][j], now + n);
      }
    }
    curk = k;
    build();
  }
  for (int i = 1; i <= n; i++) {
    int ans = 0, s = i, e = i;
    for (int j = 17; j >= 0; j--) {
      int S = get(j, s, e, 0), E = get(j, s, e, 1);
      if (s < 1) {
        int lo = max(n - abs(s), 1), hi = n;
        int now = get(j, lo, hi, 0);
        S = min(S, -(n - now));
      }
      if (e > n) {
        int lo = 1, hi = min(n, e - n);
        int now = get(j, lo, hi, 1);
        E = max(E, now + n);
      }
      if (E - S + 1 < n) {
        s = S;
        e = E;
        ans += (1 << j);
      }
    }
    if (n == 1)
      cout << 0 << " ";
    else
      printf("%d ", ans + 1);
  }
}
