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;
int a[300000];
int tree[19][1 << 20], tree2[19][1 << 20];
int arr[300000], arr2[300000];
int build(int s, int e, int i, int *tree, int *arr) {
  for (i = 0; i < 3 * n; i++) tree[i + 3 * n] = arr[i];
  for (i = 3 * n - 1; i > 0; i--)
    tree[i] = max(tree[i << 1], tree[(i << 1) | 1]);
  return 0;
}
int query(int s, int e, int qs, int qe, int i, int *tree) {
  int ans = -1e9;
  qs += 3 * n, qe += 3 * n + 1;
  while (qs < qe) {
    if (qs & 1) ans = max(ans, tree[qs++]);
    if (qe & 1) ans = max(ans, tree[--qe]);
    qs >>= 1, qe >>= 1;
  }
  return ans;
}
int ans[100000];
int main() {
  int i;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &a[i]), a[i + n] = a[i + 2 * n] = a[i];
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  int j;
  for (i = 0; i < 3 * n; i++)
    arr[i] = -max(i - a[i], 0), arr2[i] = min(i + a[i], 3 * n - 1);
  build(0, 3 * n - 1, 0, tree[0], arr), build(0, 3 * n - 1, 0, tree2[0], arr2);
  for (i = 1; (1 << i) < 3 * n; i++) {
    for (j = 0; j < 3 * n; j++) {
      int ll = -arr[j], rr = arr2[j];
      arr[j] = query(0, 3 * n - 1, ll, rr, 0, tree[i - 1]);
      arr2[j] = query(0, 3 * n - 1, ll, rr, 0, tree2[i - 1]);
    }
    build(0, 3 * n - 1, 0, tree[i], arr),
        build(0, 3 * n - 1, 0, tree2[i], arr2);
  }
  int logn = i, p = -1;
  for (i = n; i < 2 * n; i++) {
    int l = i, r = i, c = 0;
    if (p == -1) {
      for (j = logn - 1; j >= 0; j--) {
        int ll = -query(0, 3 * n - 1, l, r, 0, tree[j]),
            rr = query(0, 3 * n - 1, l, r, 0, tree2[j]);
        if (rr - ll + 1 < n) c |= (1 << j), l = ll, r = rr;
      }
      c++;
    } else {
      p = max(p - 1, 0);
      for (j = logn - 1; j >= 0; j--) {
        if (p & (1 << j)) {
          int ll = -query(0, 3 * n - 1, l, r, 0, tree[j]),
              rr = query(0, 3 * n - 1, l, r, 0, tree2[j]);
          c |= (1 << j), l = ll, r = rr;
        }
      }
      if (r - l + 1 < n) {
        j = 0;
        int ll = -query(0, 3 * n - 1, l, r, 0, tree[j]),
            rr = query(0, 3 * n - 1, l, r, 0, tree2[j]);
        c++, l = ll, r = rr;
      }
      if (r - l + 1 < n) {
        j = 0;
        int ll = -query(0, 3 * n - 1, l, r, 0, tree[j]),
            rr = query(0, 3 * n - 1, l, r, 0, tree2[j]);
        c++, l = ll, r = rr;
      }
    }
    p = ans[i - n] = c;
  }
  for (i = 0; i < n; i++) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}
