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 = 100005;
int n, a[N];
struct Right {
  int mx[N], st[17][N];
  inline int& operator[](const int& x) { return mx[x]; }
  void init() {
    memcpy(*st, mx, sizeof mx);
    for (int i = 1; i < 17; ++i)
      for (int j = 1; j + (1 << (i - 1)) <= n; ++j)
        st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
  }
  inline int query(int l, int r) {
    if (l > r) return -(1 << 30);
    const int g = (31 ^ __builtin_clz(r - l + 1));
    return max(st[g][l], st[g][r - (1 << g) + 1]);
  }
  inline int Q(int l, int r) {
    return max({query(max(l, 1), min(r, n)),
                n + query(max(l, n + 1) - n, min(r, 2 * n) - n),
                -n + query(max(l, -n + 1) + n, min(r, 0) + n)});
  }
} R[17];
struct Left {
  int mn[N], st[17][N];
  inline int& operator[](const int& x) { return mn[x]; }
  void init() {
    memcpy(*st, mn, sizeof mn);
    for (int i = 1; i < 17; ++i)
      for (int j = 1; j + (1 << (i - 1)) <= n; ++j)
        st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
  }
  inline int query(int l, int r) {
    if (l > r) return 1 << 30;
    const int g = (31 ^ __builtin_clz(r - l + 1));
    return min(st[g][l], st[g][r - (1 << g) + 1]);
  }
  inline int Q(int l, int r) {
    return min({query(max(l, 1), min(r, n)),
                n + query(max(l, n + 1) - n, min(r, 2 * n) - n),
                -n + query(max(l, -n + 1) + n, min(r, 0) + n)});
  }
} L[17];
void init() {
  for (int i = 1; i < 17; ++i) {
    L[i - 1].init();
    R[i - 1].init();
    for (int j = 1; j <= n; ++j)
      L[i][j] = L[i - 1].Q(L[i - 1][j], R[i - 1][j]),
      R[i][j] = R[i - 1].Q(L[i - 1][j], R[i - 1][j]);
  }
  L[16].init(), R[16].init();
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  if (n == 1) return puts("0"), 0;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  for (int i = 1; i <= n; ++i) R[0][i] = i + a[i], L[0][i] = i - a[i];
  init();
  for (int i = 1; i <= n; ++i) {
    int ans = 0, l = i, r = i;
    for (int j = 16; ~j; --j) {
      int nL = L[j].Q(l, r), nR = R[j].Q(l, r);
      if (nR - nL + 1 < n) ans |= 1 << j, l = nL, r = nR;
    }
    printf("%d ", ans + 1);
  }
  return 0;
}
