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>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
using namespace std;
const int N = 110002;
const int Lg = 16;
int n, a[N], m;
int l[Lg][N * 3], r[Lg][N * 3];
int tmin[Lg][N * 3 * 4], tmax[Lg][N * 3 * 4];
int x, y;
void read(int &x) {
  char ch = getchar();
  x = 0;
  for (; ch < '0' || ch > '9'; ch = getchar())
    ;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
}
inline int Min(int a, int b) { return a < b ? a : b; }
inline int Max(int a, int b) { return a > b ? a : b; }
int build(int t[], int a[], int node, int L, int r, int (*M)(int, int)) {
  int mid = (L + r) >> 1;
  return L == r ? t[node] = a[L]
                : t[node] = M(build(t, a, (node << 1), L, mid, M),
                              build(t, a, (node << 1 | 1), mid + 1, r, M));
}
int query(int t[], int node, int L, int r, int (*M)(int, int)) {
  if (L >= x && r <= y) return t[node];
  int mid = (L + r) >> 1, ans = -1, v;
  if (x <= mid) {
    v = query(t, (node << 1), L, mid, M);
    ans = (ans == -1 ? v : M(ans, v));
  };
  if (y > mid) {
    v = query(t, (node << 1 | 1), mid + 1, r, M);
    ans = (ans == -1 ? v : M(ans, v));
  };
  return ans;
}
int main() {
  read(n);
  m = n * 3;
  for (int i = (0); i < (n); i++) read(a[i]);
  for (int i = (0); i < (m); i++)
    l[0][i] = max(i - a[i % n], 0), r[0][i] = min(i + a[i % n], m - 1);
  build(tmin[0], l[0], 1, 0, m - 1, Min);
  build(tmax[0], r[0], 1, 0, m - 1, Max);
  for (int i = (1); i < (Lg); i++) {
    for (int j = (0); j < (m); j++) {
      x = l[i - 1][j], y = r[i - 1][j];
      l[i][j] = query(tmin[i - 1], 1, 0, m - 1, Min);
      r[i][j] = query(tmax[i - 1], 1, 0, m - 1, Max);
    }
    build(tmin[i], l[i], 1, 0, m - 1, Min);
    build(tmax[i], r[i], 1, 0, m - 1, Max);
  }
  for (int i = (n); i < (n << 1); i++) {
    int L = i, R = i, ans = 0;
    for (int j = (Lg - 1); j >= (0); j--) {
      x = L, y = R;
      int LL = query(tmin[j], 1, 0, m - 1, Min),
          RR = query(tmax[j], 1, 0, m - 1, Max);
      if (RR - LL + 1 < n) {
        ans += 1 << j;
        L = LL;
        R = RR;
        if (R - L + 1 == n - 1) break;
      }
    }
    if (n == 1) ans = -1;
    printf("%d ", ans + 1);
  }
  puts("");
  return 0;
}
