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;
template <typename T>
T Abs(T first) {
  return (first < 0 ? -first : first);
}
template <typename T>
T Sqr(T first) {
  return (first * first);
}
string plural(string s) {
  return (int((s).size()) && s[int((s).size()) - 1] == 'x' ? s + "en"
                                                           : s + "s");
}
const int INF = (int)1e9;
const long double EPS = 1e-12;
const long double PI = acos(-1.0);
bool Read(int &first) {
  char c, r = 0, n = 0;
  first = 0;
  for (;;) {
    c = getchar();
    if ((c < 0) && (!r)) return (0);
    if ((c == '-') && (!r))
      n = 1;
    else if ((c >= '0') && (c <= '9'))
      first = first * 10 + c - '0', r = 1;
    else if (r)
      break;
  }
  if (n) first = -first;
  return (1);
}
bool ReadLL(long long &first) {
  char c, r = 0, n = 0;
  first = 0;
  for (;;) {
    c = getchar();
    if ((c < 0) && (!r)) return (0);
    if ((c == '-') && (!r))
      n = 1;
    else if ((c >= '0') && (c <= '9'))
      first = first * 10 + c - '0', r = 1;
    else if (r)
      break;
  }
  if (n) first = -first;
  return (1);
}
int V[1100005];
int sz, tree[19][1100005][2];
int q1, q2;
void Update(int t, int i, int v1, int v2) {
  i += sz;
  while (i) {
    tree[t][i][0] = min(tree[t][i][0], v1);
    tree[t][i][1] = max(tree[t][i][1], v2);
    i >>= 1;
  }
}
void Query(int t, int i, int r1, int r2, int a, int b) {
  if (a <= r1 && r2 <= b) {
    q1 = min(q1, tree[t][i][0]);
    q2 = max(q2, tree[t][i][1]);
    return;
  }
  i <<= 1;
  int m = (r1 + r2) >> 1;
  if (a <= m) Query(t, i, r1, m, a, b);
  if (b > m) Query(t, i + 1, m + 1, r2, a, b);
}
void Query2(int t, int a, int b) {
  q1 = INF;
  q2 = -INF;
  Query(t, 1, 0, sz - 1, a, b);
}
int main() {
  if (0) freopen("in.txt", "r", stdin);
  int N, M, K;
  int i, j, k, k2, first, second, z, a, b, c, w, t;
  Read(N);
  if (N == 1) {
    printf("0\n");
    return (0);
  }
  M = N * 3;
  for (sz = 1; sz < M; sz <<= 1)
    ;
  for (t = 0; t < 19; t++)
    for (i = 0; i < (sz << 1); i++) {
      tree[t][i][0] = INF;
      tree[t][i][1] = -INF;
    }
  for (i = 0; i < N; i++) {
    int v;
    Read(v);
    for (j = 0; j < 3; j++) {
      k = N * j + i;
      Update(0, k, max(0, k - v), min(M - 1, k + v));
    }
  }
  for (t = 0; t < 18; t++)
    for (i = 0; i < M; i++) {
      Query2(t, i, i);
      a = q1, b = q2;
      Query2(t, a, b);
      Update(t + 1, i, q1, q2);
    }
  for (i = 0; i < N; i++) {
    a = b = N + i;
    int ans = 0;
    for (t = (19) - 1; t >= 0; t--) {
      Query2(t, a, b);
      if (q2 - q1 < N - 1) {
        a = q1;
        b = q2;
        ans += (1 << t);
      }
    }
    printf("%d ", ans + 1);
  }
  printf("\n");
  return (0);
}
