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 N = 3e5 + 5;
struct node {
  int l, r;
  node(int rl = 0x3f3f3f3f, int rr = 0) {
    l = rl;
    r = rr;
  }
} tree[19][N << 2], nd[N];
int n, m, a[N], b[N], ans[N], lmt;
void pushup(int level, int u) {
  tree[level][u].l = min(tree[level][u << 1].l, tree[level][u << 1 | 1].l);
  tree[level][u].r = max(tree[level][u << 1].r, tree[level][u << 1 | 1].r);
}
void build(int level, int l, int r, int u) {
  if (l == r) {
    tree[level][u] = nd[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(level, l, mid, u << 1);
  build(level, mid + 1, r, u << 1 | 1);
  pushup(level, u);
}
node query(int level, int L, int R, int l, int r, int u) {
  if (L <= l && r <= R) {
    return tree[level][u];
  }
  node rep, rrep;
  int mid = (l + r) >> 1;
  if (L <= mid) {
    rrep = query(level, L, R, l, mid, u << 1);
    rep.l = min(rep.l, rrep.l);
    rep.r = max(rep.r, rrep.r);
  }
  if (mid < R) {
    rrep = query(level, L, R, mid + 1, r, u << 1 | 1);
    rep.l = min(rep.l, rrep.l);
    rep.r = max(rep.r, rrep.r);
  }
  return rep;
}
int main() {
  scanf("%d", &n);
  m = 3 * n;
  lmt = n << 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    b[i] = a[i];
  }
  for (int i = 1, j; i <= n; i++) {
    j = i;
    nd[j] = node(j - a[i], j + b[i]);
    j += n;
    nd[j] = node(j - a[i], j + b[i]);
    j += n;
    nd[j] = node(j - a[i], j + b[i]);
  }
  build(0, 1, m, 1);
  for (int i = 1, ls, rs; i < 19; i++) {
    for (int j = 1; j <= m; j++) {
      ls = nd[j].l;
      rs = nd[j].r;
      nd[j] = query(i - 1, ls, rs, 1, m, 1);
    }
    build(i, 1, m, 1);
  }
  for (int i = n + 1, ls, rs, repl, repr; i <= lmt; i++) {
    ls = rs = i;
    node rep;
    for (int j = 18; ~j; j--) {
      rep = query(j, ls, rs, 1, m, 1);
      repl = rep.l;
      repr = rep.r;
      if (repr - repl + 1 < n) {
        ls = repl;
        rs = repr;
        ans[i - n] |= (1 << j);
      }
    }
    if (rs - ls + 1 < n) {
      ans[i - n]++;
    }
  }
  for (int i = 1; i <= n; i++) {
    printf("%d%c", ans[i], " \n"[i == n]);
  }
  return 0;
}
