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>
int n, lg[300010], a[300010], vl[300010], vr[300010], l[300010][20],
    r[300010][20];
template <typename COMP>
struct ST {
  int st[300010][20];
  COMP cmp;
  int operator()(int const &l, int const &r) {
    int k = lg[r - l + 1];
    return cmp(st[l][k], st[r - (1 << k) + 1][k]);
  }
  void init() {
    for (int i = 1; i <= 3 * n; i++) st[i][0] = i;
    for (int j = 1; j <= lg[3 * n]; j++)
      for (int i = 1; i + (1 << j) - 1 <= 3 * n; i++)
        st[i][j] = cmp(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
  }
};
struct Max {
  int operator()(int const &x, int const &y) { return vr[x] < vr[y] ? y : x; }
};
struct Min {
  int operator()(int const &x, int const &y) { return vl[x] > vl[y] ? y : x; }
};
ST<Max> rmqr;
ST<Min> rmql;
int main() {
  scanf("%d", &n);
  if (n == 1) return puts("0"), 0;
  for (int i = 2; i <= n * 3; i++) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; i++)
    scanf("%d", a + i), a[i + n] = a[i + n + n] = a[i];
  for (int i = 1; i <= 3 * n; i++) {
    vl[i] = l[i][0] = std::max(1, i - a[i]);
    vr[i] = r[i][0] = std::min(3 * n, i + a[i]);
  }
  rmql.init(), rmqr.init();
  for (int i = 1; i <= lg[3 * n]; i++)
    for (int j = 1; j <= 3 * n; j++) {
      int posl = rmql(l[j][i - 1], r[j][i - 1]),
          posr = rmqr(l[j][i - 1], r[j][i - 1]);
      l[j][i] = std::min(l[posl][i - 1], l[posr][i - 1]),
      r[j][i] = std::max(r[posl][i - 1], r[posr][i - 1]);
    }
  for (int j = n + 1; j <= n * 2; j++) {
    int u = j, v = j, ans = 0;
    for (int i = lg[3 * n]; ~i; i--)
      if (std::max(r[v][i], r[u][i]) - std::min(l[u][i], l[v][i]) + 1 < n) {
        int nu = rmql(l[u][i], r[v][i]), nv = rmqr(l[u][i], r[v][i]);
        u = nu, v = nv, ans |= 1 << i;
      }
    printf("%d ", ans + 1);
  }
  return 0;
}
