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 nmax = 3e5 + 42, MX = (1 << 20) + 42;
int n, inp[nmax];
pair<int, int> tree[20][MX];
pair<int, int> my_merge(pair<int, int> le, pair<int, int> ri) {
  return {min(le.first, ri.first), max(le.second, ri.second)};
}
void build(int node, int l, int r) {
  if (l == r) {
    tree[0][node] = {max(1, l - inp[l]), min(3 * n, l + inp[l])};
    return;
  }
  int av = (l + r) / 2;
  build(node * 2, l, av);
  build(node * 2 + 1, av + 1, r);
  tree[0][node] = my_merge(tree[0][node * 2], tree[0][node * 2 + 1]);
}
pair<int, int> query(int id, int node, int l, int r, int lq, int rq) {
  if (l == lq && r == rq) return tree[id][node];
  pair<int, int> ret = {1e9, 0};
  int av = (l + r) / 2;
  if (lq <= av)
    ret = my_merge(ret, query(id, node * 2, l, av, lq, min(av, rq)));
  if (av < rq)
    ret =
        my_merge(ret, query(id, node * 2 + 1, av + 1, r, max(av + 1, lq), rq));
  return ret;
}
void build_other(int id, int node, int l, int r) {
  if (l == r) {
    tree[id][node] = query(id - 1, 1, 1, 3 * n, tree[id - 1][node].first,
                           tree[id - 1][node].second);
    return;
  }
  int av = (l + r) / 2;
  build_other(id, node * 2, l, av);
  build_other(id, node * 2 + 1, av + 1, r);
  tree[id][node] = my_merge(tree[id][node * 2], tree[id][node * 2 + 1]);
}
int main() {
  scanf("%i", &n);
  for (int i = 1; i <= n; i++) scanf("%i", &inp[i]);
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  for (int i = n + 1; i <= 3 * n; i++) inp[i] = inp[i - n];
  build(1, 1, 3 * n);
  for (int sz = 1; sz < 20; sz++) {
    build_other(sz, 1, 1, 3 * n);
  }
  for (int i = 1; i <= n; i++) {
    int outp = 0;
    pair<int, int> active = {i + n, i + n};
    for (int sz = 19; sz >= 0; sz--) {
      pair<int, int> cur = query(sz, 1, 1, 3 * n, active.first, active.second);
      if (cur.second - cur.first + 1 < n) {
        outp += (1 << sz);
        active = cur;
      }
    }
    printf("%i ", outp + 1);
  }
  return 0;
}
