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 = (1 << 17);
const int L = 16;
int r[N];
int segm[L][2][2 * N + 10];
int n;
int clamp(int x, int a, int b) {
  if (x <= a) return a;
  if (x >= b) return b;
  return x;
}
int getl(const int a, const int b, int l, int r, int v, const int k) {
  if (l > b || r < a) return a;
  if (l >= a && r <= b) return segm[k][0][v];
  return min(getl(a, b, l, ((l + r) / 2), 2 * v, k),
             getl(a, b, ((l + r) / 2) + 1, r, 2 * v + 1, k));
}
int getr(const int a, const int b, int l, int r, int v, const int k) {
  if (l > b || r < a) return b;
  if (l >= a && r <= b) return segm[k][1][v];
  return max(getr(a, b, l, ((l + r) / 2), 2 * v, k),
             getr(a, b, ((l + r) / 2) + 1, r, 2 * v + 1, k));
}
int ql(int a, int b, int k) {
  int sol = a;
  if (a < 0) {
    sol = min(sol, getl(n + a, n - 1, 0, N - 1, 1, k) - n);
    a = 0;
  }
  if (b >= n) {
    sol = min(sol, getl(0, b - n, 0, N - 1, 1, k) + n);
    b = n - 1;
  }
  sol = min(sol, getl(a, b, 0, N - 1, 1, k));
  sol = clamp(sol, -n + 1, 2 * n - 1);
  return sol;
}
int qr(int a, int b, int k) {
  int sol = b;
  if (a < 0) {
    sol = max(sol, getr(n + a, n - 1, 0, N - 1, 1, k) - n);
    a = 0;
  }
  if (b >= n) {
    sol = max(sol, getr(0, b - n, 0, N - 1, 1, k) + n);
    b = n - 1;
  }
  sol = max(sol, getr(a, b, 0, N - 1, 1, k));
  sol = clamp(sol, -n + 1, 2 * n - 1);
  return sol;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &r[i]);
  }
  for (int i = 0; i < n; i++)
    segm[0][0][N + i] = clamp(i - r[i], -n + 1, 2 * n - 1);
  for (int i = 0; i < n; i++)
    segm[0][1][N + i] = clamp(i + r[i], -n + 1, 2 * n - 1);
  for (int i = N - 1; i > 0; i--) {
    segm[0][0][i] = min(segm[0][0][2 * i], segm[0][0][2 * i + 1]);
    segm[0][1][i] = max(segm[0][1][2 * i], segm[0][1][2 * i + 1]);
  }
  for (int k = 1; k < L; k++) {
    for (int i = 0; i < n; i++) {
      segm[k][0][N + i] =
          ql(segm[k - 1][0][N + i], segm[k - 1][1][N + i], k - 1);
      segm[k][1][N + i] =
          qr(segm[k - 1][0][N + i], segm[k - 1][1][N + i], k - 1);
    }
    for (int i = N - 1; i > 0; i--) {
      segm[k][0][i] = min(segm[k][0][2 * i], segm[k][0][2 * i + 1]);
      segm[k][1][i] = max(segm[k][1][2 * i], segm[k][1][2 * i + 1]);
    }
  }
  for (int i = 0; i < n; i++) {
    int l = i, r = i;
    int sol = 0;
    for (int k = L - 1; k >= 0; k--) {
      int nl = ql(l, r, k);
      int nr = qr(l, r, k);
      if (nr - nl <= n - 1) {
        l = nl;
        r = nr;
        sol += (1 << k);
      }
    }
    if (r - l < n - 1) sol++;
    printf("%d ", sol);
  }
  printf("\n");
  return 0;
}
