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 = 1000 * 100 + 10, M = 18;
int nxt[M][N], prv[M][N];
int seg[M][4 * N][2];
int n;
void build(int id, bool f, int s = 0, int e = N, int ind = 1) {
  if (e - s == 1) {
    seg[id][ind][f] = (f ? nxt[id][s] : prv[id][s]);
    return;
  }
  int mid = (s + e) / 2;
  build(id, f, s, mid, 2 * ind);
  build(id, f, mid, e, 2 * ind + 1);
  if (f)
    seg[id][ind][f] = max(seg[id][2 * ind][f], seg[id][2 * ind + 1][f]);
  else
    seg[id][ind][f] = min(seg[id][2 * ind][f], seg[id][2 * ind + 1][f]);
}
int Get(int id, int f, int l, int r, int s = 0, int e = N, int ind = 1) {
  if (l <= s && e <= r) return seg[id][ind][f];
  if (r <= s || e <= l) return (f ? -N * 100 : N * 100);
  int mid = (s + e) / 2;
  int v1 = Get(id, f, l, r, s, mid, 2 * ind);
  int v2 = Get(id, f, l, r, mid, e, 2 * ind + 1);
  if (f)
    return max(v1, v2);
  else
    return min(v1, v2);
}
int get(int id, int f, int l, int r) {
  if (r > n) return max(Get(id, f, l, n), Get(id, f, 0, r - n) + n);
  if (l < 0) return min(Get(id, f, l + n, n) - n, Get(id, f, 0, r));
  return Get(id, f, l, r);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  if (n == 1) return cout << 0 << endl, 0;
  for (int i = 0; i < n; i++) {
    int t;
    cin >> t;
    nxt[0][i] = i + t;
    prv[0][i] = i - t;
  }
  for (int i = 1; i < M; i++) {
    build(i - 1, 1);
    for (int j = 0; j < n; j++) {
      int x = get(i - 1, 1, max(0, prv[i - 1][j]), nxt[i - 1][j] + 1);
      nxt[i][j] = min(2 * n - 1, x);
    }
    build(i - 1, 0);
    for (int j = 0; j < n; j++) {
      int x = get(i - 1, 0, prv[i - 1][j], min(n - 1, nxt[i - 1][j]) + 1);
      prv[i][j] = max(-n + 1, x);
    }
  }
  for (int i = 0; i < n; i++) {
    int l = i, r = i, ans = 0;
    for (int j = M - 2; j > -1; j--) {
      int p = get(j, 0, l, min(n, r + 1));
      int q = get(j, 1, max(l, 0), r + 1);
      q = min(q, 2 * n - 1);
      p = max(p, -n + 1);
      bool f = 0;
      if (p <= 0 && q >= n - 1) f = 1;
      if (p < 0 && p + n - 1 <= q) f = 1;
      if (q > n - 1 && q - n + 1 >= p) f = 1;
      if (!f) {
        ans += (1 << j);
        l = p;
        r = q;
      }
    }
    cout << ans + 1 << ' ';
  }
  cout << endl;
}
