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 segmenttree {
  int tree[65536 * 4 * 2 + 10];
  void update(int x, int y) {
    x = x + 65536 * 4 - 1;
    tree[x] = y;
    x = x / 2;
    while (x) tree[x] = max(tree[x * 2], tree[x * 2 + 1]), x = x / 2;
  }
  int query(int a, int b, int l, int r, int id) {
    if (l >= a and r <= b) return tree[id];
    int mid = (l + r) / 2;
    int sm = -1e9;
    if (a <= mid) sm = max(sm, query(a, b, l, mid, id * 2));
    if (b > mid) sm = max(sm, query(a, b, mid + 1, r, id * 2 + 1));
    return sm;
  }
  void upd(int x, int y) { update(x + 1, y); }
  int ask(int l, int r) { return query(l + 1, r + 1, 1, 65536 * 4, 1); }
} sl[18 + 2], sr[18 + 2];
int n;
int r[65536 * 4];
pair<int, int> range[65536 * 4][18 + 2];
int ans[65536 * 4];
int main() {
  cin >> n;
  if (n == 1) {
    cout << 0;
    exit(0);
  }
  for (int i = 0; i < n; i++)
    scanf("%d", &r[i]),
        range[i][0] = make_pair(max(0, i - r[i]), min(i + r[i], n + n - 1));
  for (int i = n; i < n + n; i++)
    r[i] = r[i - n],
    range[i][0] = make_pair(max(0, i - r[i]), min(i + r[i], n + n - 1));
  n = n + n;
  for (int i = 1; i <= 18; i++) {
    for (int j = 0; j < n; j++)
      sl[i - 1].upd(j, -range[j][i - 1].first),
          sr[i - 1].upd(j, range[j][i - 1].second);
    for (int j = 0; j < n; j++) {
      int l = range[j][i - 1].first, r = range[j][i - 1].second;
      int cl = -sl[i - 1].ask(l, r), cr = sr[i - 1].ask(l, r);
      range[j][i] = make_pair(cl, cr);
    }
  }
  for (int i = 0; i < n; i++) {
    int res = 0;
    int x = i;
    int l = i, r = i;
    for (int j = 18 - 1; ~j; j--) {
      int cl = -sl[j].ask(l, r), cr = sr[j].ask(l, r);
      if (cr - cl + 1 < n / 2) l = cl, r = cr, res += (1 << j);
    }
    ans[i] = res + 1;
  }
  for (int i = 0; i < n / 2; i++) printf("%d ", min(ans[i], ans[i + n / 2]));
  return 0;
}
