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;
struct SGT {
  int minn[1200000], maxn[1200000];
  inline void pushup(int o) {
    minn[o] = min(minn[o * 2], minn[o * 2 + 1]);
    maxn[o] = max(maxn[o * 2], maxn[o * 2 + 1]);
  }
  void build(int l, int r, int o, int *fir1, int *fir2) {
    if (l == r) {
      minn[o] = fir1[l];
      maxn[o] = fir2[l];
    } else {
      int m = ((l + r) >> 1);
      build(l, m, o * 2, fir1, fir2);
      build(m + 1, r, o * 2 + 1, fir1, fir2);
      pushup(o);
    }
  }
  pair<int, int> query(int l, int r, int o, int lx, int rx) {
    if (l >= lx && r <= rx)
      return pair<int, int>(minn[o], maxn[o]);
    else {
      int m = ((l + r) >> 1);
      if (m >= rx) return query(l, m, o * 2, lx, rx);
      if (m < lx) return query(m + 1, r, o * 2 + 1, lx, rx);
      pair<int, int> a = query(l, m, o * 2, lx, rx),
                     b = query(m + 1, r, o * 2 + 1, lx, rx);
      return pair<int, int>(min(a.first, b.first), max(a.second, b.second));
    }
  }
} tr[20];
int l[20][300005], r[20][300005];
int num[300005];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &num[i]);
    num[2 * n + i] = num[n + i] = num[i];
  }
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= 3 * n; i++) {
    l[0][i] = max(1, i - num[i]);
    r[0][i] = min(3 * n, i + num[i]);
  }
  tr[0].build(1, 3 * n, 1, l[0], r[0]);
  for (int i = 1; i < 20; i++) {
    for (int j = 1; j <= 3 * n; j++) {
      pair<int, int> t = tr[i - 1].query(1, 3 * n, 1, l[i - 1][j], r[i - 1][j]);
      l[i][j] = t.first;
      r[i][j] = t.second;
    }
    tr[i].build(1, 3 * n, 1, l[i], r[i]);
  }
  for (int i = 1; i <= n; i++) {
    int nl = n + i, nr = n + i, ans = 0;
    for (int j = 19; j >= 0; j--) {
      pair<int, int> t = tr[j].query(1, 3 * n, 1, nl, nr);
      if (t.second - t.first + 1 < n) {
        ans += (1 << j);
        nl = t.first;
        nr = t.second;
      }
    }
    printf("%d ", ans + 1);
  }
  printf("\n");
  return 0;
}
