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 = 300005, LG = 20;
int n, A[N], L[LG][N], R[LG][N], MN[LG][N * 2], MX[LG][N * 2];
inline void Build(int j) {
  for (int i = 1; i <= n * 3; i++)
    MN[j][i + n * 3 - 1] = L[j][i], MX[j][i + n * 3 - 1] = R[j][i];
  for (int i = n * 3 - 1; i; i--)
    MN[j][i] = min(MN[j][i + i], MN[j][i + i + 1]),
    MX[j][i] = max(MX[j][i + i], MX[j][i + i + 1]);
}
inline int GetMin(int l, int r, int j) {
  int Mn = INT_MAX;
  l--;
  for (l += n * 3, r += n * 3; l < r; l >>= 1, r >>= 1) {
    if (l & 1) Mn = min(Mn, MN[j][l]), l++;
    if (r & 1) r--, Mn = min(Mn, MN[j][r]);
  }
  return (Mn);
}
inline int GetMax(int l, int r, int j) {
  int Mx = INT_MIN;
  l--;
  for (l += n * 3, r += n * 3; l < r; l >>= 1, r >>= 1) {
    if (l & 1) Mx = max(Mx, MX[j][l]), l++;
    if (r & 1) r--, Mx = max(Mx, MX[j][r]);
  }
  return (Mx);
}
int main() {
  scanf("%d", &n);
  if (n == 1) return !printf("0");
  for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
  for (int i = n + 1; i <= n * 3; i++) A[i] = A[i - n];
  for (int i = 1; i <= n * 3; i++)
    L[0][i] = max(i - A[i], 1), R[0][i] = min(i + A[i], n * 3);
  memset(MN, 63, sizeof(MN));
  memset(MX, -63, sizeof(MX));
  Build(0);
  for (int j = 1; j < LG; j++) {
    for (int i = 1; i <= n * 3; i++)
      L[j][i] = GetMin(L[j - 1][i], R[j - 1][i], j - 1),
      R[j][i] = GetMax(L[j - 1][i], R[j - 1][i], j - 1);
    Build(j);
  }
  for (int i = n + 1; i <= n + n; i++) {
    int l = i, r = i, c = 0;
    for (int j = LG - 1; ~j; j--) {
      int le = GetMin(l, r, j), ri = GetMax(l, r, j);
      if (ri - le + 1 < n) l = le, r = ri, c += (1 << j);
    }
    printf("%d ", c + 1);
  }
  return (0);
}
