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;
int n, a[100007 * 3];
pair<int, int> seg[17][100007 * 3], Seg[17][100007 * 12];
void Build(int i, int k, int l, int r) {
  if (l == r) {
    Seg[i][k] = seg[i][l];
    return;
  }
  int mid = (l + r) >> 1;
  Build(i, k * 2, l, mid);
  Build(i, k * 2 + 1, mid + 1, r);
  Seg[i][k].first = min(Seg[i][k * 2].first, Seg[i][k * 2 + 1].first);
  Seg[i][k].second = max(Seg[i][k * 2].second, Seg[i][k * 2 + 1].second);
}
int fst, sec;
void Get(int i, int k, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    fst = min(fst, Seg[i][k].first);
    sec = max(sec, Seg[i][k].second);
    return;
  }
  int res = 1, mid = (l + r) >> 1;
  if (L <= mid) Get(i, k * 2, l, mid, L, R);
  if (R > mid) Get(i, k * 2 + 1, mid + 1, r, L, R);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    a[n + i] = a[n * 2 + i] = a[i];
  }
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= n * 3; ++i) {
    seg[0][i].first = max(i - a[i], 1);
    seg[0][i].second = min(i + a[i], n * 3);
  }
  Build(0, 1, 1, n * 3);
  for (int i = 1; i < 17; ++i) {
    for (int j = 1; j <= n * 3; ++j) {
      fst = seg[i - 1][j].first, sec = seg[i - 1][j].second;
      Get(i - 1, 1, 1, n * 3, fst, sec);
      seg[i][j].first = fst, seg[i][j].second = sec;
    }
    Build(i, 1, 1, n * 3);
  }
  for (int i = 1; i <= n; ++i) {
    int ans = n, cur = 0, l = n + i, r = n + i;
    for (int j = 16; j >= 0; --j) {
      fst = l, sec = r;
      Get(j, 1, 1, n * 3, l, r);
      if (sec - fst + 1 >= n)
        ans = min(ans, cur + (1 << j));
      else
        l = fst, r = sec, cur += 1 << j;
    }
    printf("%d%c", ans, " \n"[i == n]);
  }
}
