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 int MAXN = (int)3e5 + 5;
const int MAX_LOG = 18;
const int MIN = 0;
const int MAX = 1;
const int INF = (int)1e9;
struct SegTree {
  SegTree() {}
  SegTree(vector<int>& v, int op) : op(op), v(v) {
    n = (int)v.size() - 1;
    tree.resize(4 * n);
    build(1, 1, n);
  }
  void build(int node, int a, int b) {
    if (a == b) {
      tree[node] = v[a];
      return;
    }
    int mid = (a + b) / 2;
    build(node * 2, a, mid);
    build(node * 2 + 1, mid + 1, b);
    if (op == MIN) {
      tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    } else {
      tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }
  }
  void update(int idx, int val) { update(1, 1, n, idx, val); }
  int query(int i, int j) { return query(1, 1, n, i, j); }

 private:
  void update(int node, int a, int b, int idx, int val) {
    if (a > b || b < idx || a > idx) {
      return;
    }
    if (idx <= a && b <= idx) {
      tree[node] += val;
      return;
    }
    int mid = (a + b) / 2;
    update(node * 2, a, mid, idx, val);
    update(node * 2 + 1, mid + 1, b, idx, val);
    if (op == MIN) {
      tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    } else {
      tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }
  }
  int query(int node, int a, int b, int i, int j) {
    if (a > b || b < i || a > j) {
      return op == MIN ? INF : 0;
    }
    if (i <= a && b <= j) {
      return tree[node];
    }
    int mid = (a + b) / 2;
    int q1 = query(node * 2, a, mid, i, j);
    int q2 = query(node * 2 + 1, mid + 1, b, i, j);
    return op == MIN ? min(q1, q2) : max(q1, q2);
  }
  int n;
  int op;
  vector<int> v;
  vector<int> tree;
};
int resp[MAXN];
SegTree tree[MAX_LOG][2];
vector<vector<int> > asdhasudha(MAX_LOG);
vector<vector<int> > oqwjapodwpq(MAX_LOG);
void build(int n) {
  for (int i = 0; i < MAX_LOG; i++) {
    asdhasudha[i] = vector<int>(3 * n + 1);
    oqwjapodwpq[i] = vector<int>(3 * n + 1);
  }
  for (int i = 1; i <= 3 * n; i++) {
    asdhasudha[0][i] = max(1, i - resp[i]);
    oqwjapodwpq[0][i] = min(3 * n, i + resp[i]);
  }
  tree[0][0] = SegTree(asdhasudha[0], MIN);
  tree[0][1] = SegTree(oqwjapodwpq[0], MAX);
  for (int k = 1; k < MAX_LOG; k++) {
    for (int i = n + 1; i <= 2 * n; i++) {
      int l = tree[k - 1][0].query(asdhasudha[k - 1][i], oqwjapodwpq[k - 1][i]);
      int r = tree[k - 1][1].query(asdhasudha[k - 1][i], oqwjapodwpq[k - 1][i]);
      asdhasudha[k][i] = l;
      oqwjapodwpq[k][i] = r;
      int delta_l = asdhasudha[k - 1][i] - l;
      int delta_r = r - oqwjapodwpq[k - 1][i];
      asdhasudha[k][i - n] = max(1, asdhasudha[k - 1][i - n] - delta_l);
      oqwjapodwpq[k][i - n] = min(3 * n, oqwjapodwpq[k - 1][i - n] + delta_r);
      asdhasudha[k][i + n] = max(1, asdhasudha[k - 1][i + n] - delta_l);
      oqwjapodwpq[k][i + n] = min(3 * n, oqwjapodwpq[k - 1][i + n] + delta_r);
    }
    tree[k][0] = SegTree(asdhasudha[k], MIN);
    tree[k][1] = SegTree(oqwjapodwpq[k], MAX);
  }
  return;
}
int solve(int pos, int n) {
  int best = 0;
  int sum = 0;
  int l = pos;
  int r = pos;
  for (int k = MAX_LOG - 1; k >= 0; k--) {
    int vl = tree[k][0].query(l, r);
    int vr = tree[k][1].query(l, r);
    if (vr - vl + 1 >= n) {
      best = sum + (1 << k);
    } else {
      sum += 1 << k;
      l = vl;
      r = vr;
    }
  }
  return best;
}
int main(void) {
  int n;
  scanf(" %d", &n);
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    scanf(" %d", &resp[i]);
  }
  for (int i = n + 1; i <= 3 * n; i++) {
    resp[i] = resp[i - n];
  }
  build(n);
  for (int i = 1; i <= n; i++) {
    int ans = solve(i + n, n);
    if (i != 1) {
      printf(" ");
    }
    printf("%d", ans);
  }
  return 0;
}
