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;
const long long MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f;
int key = 524288;
struct idxtree {
  int tree[1050000];
  void init() {
    int i;
    for (i = 0; i < key * 2; i++) tree[i] = -INF;
  }
  void upd(int idx, int val) {
    idx += key;
    while (idx) {
      tree[idx] = max(tree[idx], val);
      idx /= 2;
    }
  }
  int getv(int s, int e) {
    s += key;
    e += key;
    int v = -INF;
    while (s <= e) {
      if (s & 1) v = max(v, tree[s]);
      if (~e & 1) v = max(v, tree[e]);
      s = (s + 1) / 2;
      e = (e - 1) / 2;
    }
    return v;
  }
  int f(int first, int tt) {
    while (first < key) {
      if (tt < 0) {
        if (tree[first] == tree[first * 2])
          first = first * 2;
        else
          first = first * 2 + 1;
      } else {
        if (tree[first] == tree[first * 2 + 1])
          first = first * 2 + 1;
        else
          first = first * 2;
      }
    }
    return first - key;
  }
  int geti(int s, int e, int tt) {
    int t = getv(s, e);
    s += key;
    e += key;
    while (s <= e) {
      if (s & 1) {
        if (tree[s] == t) return f(s, tt);
      }
      if (~e & 1) {
        if (tree[e] == t) return f(e, tt);
      }
      s = (s + 1) / 2;
      e = (e - 1) / 2;
    }
    return -1;
  }
} mt, Mt;
int n;
int arr[300100];
int le[300100][20], re[300100][20];
int main() {
  int i;
  scanf("%d", &n);
  for (i = 0; i < n; i++) scanf("%d", &arr[i]);
  for (i = n; i < 3 * n; i++) arr[i] = arr[i - n];
  mt.init();
  Mt.init();
  for (i = 0; i < 3 * n; i++) {
    Mt.upd(i, i + arr[i]);
    mt.upd(i, arr[i] - i);
  }
  for (i = n; i < 2 * n; i++) {
    le[i][0] = i - arr[i];
    re[i][0] = i + arr[i];
  }
  for (i = 0; i < n; i++) {
    le[i][0] = max(le[i + n][0] - n, 0);
    re[i][0] = max(re[i + n][0] - n, 0);
  }
  for (i = 2 * n; i < 3 * n; i++) {
    le[i][0] = min(le[i - n][0] + n, 3 * n - 1);
    re[i][0] = min(re[i - n][0] + n, 3 * n - 1);
  }
  int j;
  for (j = 1; j < 20; j++) {
    for (i = 0; i < 3 * n; i++) {
      int lt = mt.geti(le[i][j - 1], re[i][j - 1], 1),
          rt = Mt.geti(le[i][j - 1], re[i][j - 1], -1);
      le[i][j] = min(le[lt][j - 1], le[rt][j - 1]);
      re[i][j] = max(re[lt][j - 1], re[rt][j - 1]);
    }
  }
  for (i = n; i < 2 * n; i++) {
    int l = i, r = i, v = 0;
    for (j = 19; j >= 0; j--) {
      int lt = mt.geti(l, r, 1), rt = Mt.geti(l, r, -1);
      if (max(re[rt][j], re[lt][j]) - min(le[rt][j], le[lt][j]) < n - 1) {
        l = min(le[rt][j], le[lt][j]);
        r = max(re[rt][j], re[lt][j]);
        v += 1 << j;
      }
    }
    if (n != 1) v++;
    printf("%d ", v);
  }
  printf("\n");
  return 0;
}
