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 K = 20;
const int N = 2e5 + 10;
const int INF = 1e9 + 7;
int n;
int a[N];
pair<int, int> rg[K][N];
pair<int, int> merge(pair<int, int> p1, pair<int, int> p2) {
  return pair<int, int>(min(p1.first, p2.first), max(p1.second, p2.second));
}
struct SegTree {
  pair<int, int> dat[N * 4];
  void build(pair<int, int> rg[], int v = 0, int l = 1, int r = n * 2 + 1) {
    if (l + 1 == r) {
      dat[v] = rg[l];
    } else {
      int mid = (l + r) / 2, chl = v * 2 + 1, chr = v * 2 + 2;
      build(rg, chl, l, mid);
      build(rg, chr, mid, r);
      dat[v] = merge(dat[chl], dat[chr]);
    }
  }
  pair<int, int> query(int L, int R, int v = 0, int l = 1, int r = n * 2 + 1) {
    if (L >= r || l >= R) return pair<int, int>(INF, -INF);
    if (L <= l && r <= R) return dat[v];
    int mid = (l + r) / 2, chl = v * 2 + 1, chr = v * 2 + 2;
    return merge(query(L, R, chl, l, mid), query(L, R, chr, mid, r));
  }
  pair<int, int> trans(pair<int, int> p) {
    return query(p.first, p.second + 1);
  }
} rmq[K];
int len(pair<int, int> p) { return p.second - p.first + 1; }
int solve(int center) {
  pair<int, int> r(center, center);
  int res = 0;
  for (int k = K - 1; k >= 0; k--) {
    pair<int, int> nr = rmq[k].trans(r);
    if (len(nr) < n) {
      r = nr;
      res += 1 << k;
    }
  }
  return res + 1;
}
int main() {
  scanf("%d", &n);
  if (n == 1) return puts("0"), 0;
  for (int i = 1; i <= n; i++) scanf("%d", a + i), a[n + i] = a[i];
  for (int i = 1; i <= 2 * n; i++) {
    rg[0][i] = pair<int, int>(max(1, i - a[i]), min(2 * n, i + a[i]));
  }
  rmq[0].build(rg[0]);
  for (int k = 1; k < K; k++) {
    for (int i = 1; i <= 2 * n; i++) {
      rg[k][i] = rmq[k - 1].trans(rg[k - 1][i]);
    }
    rmq[k].build(rg[k]);
  }
  for (int i = 1; i <= n; i++) {
    int ans = min(solve(i), solve(i + n));
    printf("%d%c", ans, " \n"[i == n]);
  }
}
