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, lg2[300010], a[300010];
class ST {
 public:
  int st[300010][19], val[300010];
  inline int cmp(int x, int y) { return (val[x] < val[y]) ? y : x; }
  void build(int* x, int len, int typ) {
    for (int i = 1; i <= len; i++) st[i][0] = i, val[i] = typ * x[i];
    for (int j = 1; j <= lg2[len]; j++) {
      for (int i = 1; i + (1 << j) - 1 <= len; i++) {
        st[i][j] = cmp(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  inline int query(int l, int r) {
    int p = lg2[r - l + 1];
    return cmp(st[l][p], st[r - (1 << p) + 1][p]);
  }
} L, R;
int l[19][300010], r[19][300010];
int main() {
  scanf("%d", &n);
  for (int i = 2; i <= 3 * n; i++) lg2[i] = lg2[i >> 1] + 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i + n] = a[i + 2 * n] = a[i];
  }
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= 3 * n; i++) {
    l[0][i] = max(1, i - a[i]);
    r[0][i] = min(3 * n, i + a[i]);
  }
  L.build(l[0], 3 * n, -1);
  R.build(r[0], 3 * n, 1);
  for (int i = 1; i <= lg2[3 * n]; i++) {
    for (int j = 1; j <= 3 * n; j++) {
      int pl = L.query(l[i - 1][j], r[i - 1][j]),
          pr = R.query(l[i - 1][j], r[i - 1][j]);
      l[i][j] = min(l[i - 1][pl], l[i - 1][pr]);
      r[i][j] = max(r[i - 1][pl], r[i - 1][pr]);
    }
  }
  for (int j = n + 1; j <= n * 2; j++) {
    int ans = 0, tl = j, tr = j;
    for (int i = lg2[3 * n]; i >= 0; i--) {
      if (max(r[i][tl], r[i][tr]) - min(l[i][tl], l[i][tr]) + 1 >= n) continue;
      int nl = L.query(l[i][tl], r[i][tr]), nr = R.query(l[i][tl], r[i][tr]);
      tl = nl, tr = nr;
      ans += (1 << i);
    }
    printf("%d ", ans + 1);
  }
  return 0;
}
