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;
template <int n>
struct seg_tree {
  int t[n * 2];
  int get(int i) { return t[i + n]; }
  void set(int i, int x) {
    t[i += n] = x;
    while (i /= 2) {
      t[i] = min(t[i * 2], t[i * 2 + 1]);
    }
  }
  int rmq(int i, int j) {
    int ans = get(i);
    for (i += n, j += n + 1; i < j; i /= 2, j /= 2) {
      if (i & 1) ans = min(ans, t[i++]);
      if (j & 1) ans = min(ans, t[--j]);
    }
    return ans;
  }
};
int n, r[(1 << 19)];
seg_tree<(1 << 19)> a[18 + 1], b[18 + 1];
int main() {
  scanf("%d", &n);
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &r[i]);
  }
  for (int i = 0; i < 3 * n; i++) {
    a[0].set(i, max(0, i - r[i % n]));
    b[0].set(i, -min(3 * n - 1, i + r[i % n]));
  }
  for (int k = 1; k <= 18; k++) {
    for (int i = 0; i < 3 * n; i++) {
      a[k].set(i, a[k - 1].rmq(a[k - 1].get(i), -b[k - 1].get(i)));
      b[k].set(i, b[k - 1].rmq(a[k - 1].get(i), -b[k - 1].get(i)));
    }
  }
  for (int i = n; i < 2 * n; i++) {
    int ans = 0, lft = i, rgt = i;
    for (int k = 18; k >= 0; k--) {
      int nl = a[k].rmq(lft, rgt), nr = -b[k].rmq(lft, rgt);
      if (nr - nl < n - 1) {
        lft = nl;
        rgt = nr;
        ans += 1 << k;
      }
    }
    if (i > n) printf(" ");
    printf("%d", ans + 1);
  }
  printf("\n");
}
