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;
inline int gi() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - 48;
    ch = getchar();
  }
  return x * f;
}
template <typename T>
inline bool Max(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool Min(T &a, T b) {
  return b < a ? a = b, 1 : 0;
}
const int N = 3e5 + 7, Nd = N << 2;
int n;
int a[N];
struct data {
  int l, r;
  data() {}
  data(int l, int r) : l(l), r(r) {}
  data operator+(const data &rhs) const {
    return data(min(l, rhs.l), max(r, rhs.r));
  }
} v[N];
struct sgt {
  data t[Nd];
  int dep;
  void build(int l, int r, int o) {
    if (l == r) {
      t[o] = v[l];
      return;
    }
    int mid = l + r >> 1;
    build(l, mid, o << 1);
    build(mid + 1, r, o << 1 | 1);
    t[o] = t[o << 1] + t[o << 1 | 1];
  }
  data query(int L, int R, int l, int r, int o) {
    if (L <= l && r <= R) return t[o];
    int mid = l + r >> 1;
    if (R <= mid) return query(L, R, l, mid, o << 1);
    if (L > mid) return query(L, R, mid + 1, r, o << 1 | 1);
    return query(L, R, l, mid, o << 1) + query(L, R, mid + 1, r, o << 1 | 1);
  }
} sg[20];
int main() {
  n = gi();
  if (n == 1) return puts("0"), 0;
  for (int i = 1; i <= n; ++i) a[i] = gi(), a[i + n] = a[i + 2 * n] = a[i];
  for (int i = 0; i <= 19; ++i) sg[i].dep = i;
  for (int i = 1; i <= 3 * n; ++i)
    v[i].l = max(1, i - a[i]), v[i].r = min(3 * n, i + a[i]);
  sg[0].build(1, 3 * n, 1);
  for (int dep = 1; dep <= 19; ++dep) {
    for (int i = 1; i <= 3 * n; ++i)
      v[i] = sg[dep - 1].query(v[i].l, v[i].r, 1, 3 * n, 1);
    sg[dep].build(1, 3 * n, 1);
  }
  for (int i = n + 1; i <= n + n; ++i) {
    data now(i, i), tmp;
    int cnt = 0;
    for (int k = 19; ~k; --k) {
      tmp = sg[k].query(now.l, now.r, 1, 3 * n, 1);
      if (tmp.r - tmp.l + 1 < n) cnt += 1 << k, now = tmp;
    }
    printf("%d%c", cnt + 1, i == n + n ? '\n' : ' ');
  }
  return 0;
}
