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 = 300005;
struct jz {
  int L, R;
  jz(int L = 0, int R = 0) : L(L), R(R) {}
} a[22][maxn * 4], lst[maxn];
int n, K, c[maxn];
inline int _read() {
  int num = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') num = num * 10 + ch - 48, ch = getchar();
  return num;
}
jz up(jz x, jz y) { return jz(min(x.L, y.L), max(x.R, y.R)); }
void add(int x, int l, int r, int w, jz a[], jz y) {
  if (l == r) {
    a[x] = y;
    return;
  }
  int mid = l + (r - l >> 1);
  if (w <= mid)
    add((x << 1), l, mid, w, a, y);
  else
    add(((x << 1) + 1), mid + 1, r, w, a, y);
  a[x] = up(a[(x << 1)], a[((x << 1) + 1)]);
}
jz ask(int x, int l, int r, int L, int R, jz a[]) {
  if (l == L && r == R) return a[x];
  int mid = l + (r - l >> 1);
  if (R <= mid)
    return ask((x << 1), l, mid, L, R, a);
  else if (L > mid)
    return ask(((x << 1) + 1), mid + 1, r, L, R, a);
  else
    return up(ask((x << 1), l, mid, L, mid, a),
              ask(((x << 1) + 1), mid + 1, r, mid + 1, R, a));
}
int work(int x) {
  jz now = jz(x, x);
  int ans = 0;
  for (int j = K; j >= 0; j--) {
    jz w = ask(1, 1, n, now.L, now.R, a[j]);
    if (w.R - w.L + 1 < n / 3) ans += (1 << j), now = w;
  }
  return ans + 1;
}
int main() {
  n = _read();
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  K = log2(n);
  for (int i = n + 1; i <= 2 * n; i++) c[i] = c[i - n] = c[i + n] = _read();
  n *= 3;
  for (int i = 0; i <= K; i++)
    for (int j = 1; j <= 4 * n; j++) a[i][j] = jz(n, 1);
  for (int i = 1; i <= n; i++)
    lst[i] = jz(max(1, i - c[i]), min(n, i + c[i])),
    add(1, 1, n, i, a[0], lst[i]);
  for (int j = 1; j <= K; j++)
    for (int i = 1; i <= n; i++) {
      lst[i] = ask(1, 1, n, lst[i].L, lst[i].R, a[j - 1]);
      add(1, 1, n, i, a[j], lst[i]);
    }
  for (int i = n / 3 + 1; i <= n / 3 * 2; i++) printf("%d ", work(i));
  return 0;
}
