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 void read(int &x) {
  int v = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void read(long long &x) {
  long long v = 0ll, f = 1ll;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-')
    f = -1;
  else
    v = (c & 15);
  while (isdigit(c = getchar())) v = (v << 1) + (v << 3) + (c & 15);
  x = v * f;
}
inline void readc(char &x) {
  char c;
  while (((c = getchar()) == ' ') || c == '\n')
    ;
  x = c;
}
int n, m, i, j, k, a[300005], f[300005][19], g[300005][19], f2[300005][19],
    g2[300005][19], vf[300005], vg[300005], lg[300005];
int qryf(int l, int r) {
  int k = lg[r - l + 1];
  if (vf[f2[l][k]] < vf[f2[r - (1 << k) + 1][k]]) {
    return f2[l][k];
  } else {
    return f2[r - (1 << k) + 1][k];
  }
}
int qryg(int l, int r) {
  int k = lg[r - l + 1];
  if (vg[g2[l][k]] > vg[g2[r - (1 << k) + 1][k]]) {
    return g2[l][k];
  } else {
    return g2[r - (1 << k) + 1][k];
  }
}
int main() {
  for ((i) = (2); (i) <= (300000); (i)++) {
    lg[i] = lg[i / 2] + 1;
  }
  read(n);
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    read(a[i]);
    a[i + n] = a[i + n + n] = a[i];
  }
  for (((i)) = (1); ((i)) <= ((n + n + n)); ((i))++) {
    f[i][0] = vf[i] = max(1, i - a[i]);
    g[i][0] = vg[i] = min(n * 3, i + a[i]);
    f2[i][0] = g2[i][0] = i;
  }
  for (((j)) = (1); ((j)) <= ((18)); ((j))++) {
    for (((i)) = (1); ((i)) <= ((n + n + n - (1 << j) + 1)); ((i))++) {
      if (vf[f2[i][j - 1]] < vf[f2[i + (1 << (j - 1))][j - 1]]) {
        f2[i][j] = f2[i][j - 1];
      } else {
        f2[i][j] = f2[i + (1 << (j - 1))][j - 1];
      }
      if (vg[g2[i][j - 1]] > vg[g2[i + (1 << (j - 1))][j - 1]]) {
        g2[i][j] = g2[i][j - 1];
      } else {
        g2[i][j] = g2[i + (1 << (j - 1))][j - 1];
      }
    }
  }
  for (((j)) = (1); ((j)) <= ((18)); ((j))++) {
    for (((i)) = (1); ((i)) <= ((n + n + n)); ((i))++) {
      int pl = qryf(f[i][j - 1], g[i][j - 1]);
      int pr = qryg(f[i][j - 1], g[i][j - 1]);
      f[i][j] = min(f[pl][j - 1], f[pr][j - 1]);
      g[i][j] = max(g[pl][j - 1], g[pr][j - 1]);
    }
  }
  for (((i)) = (1); ((i)) <= ((n)); ((i))++) {
    int ans = 0, x = i + n, y = i + n;
    for ((j) = (18); (j) >= (0); (j)--) {
      if (max(g[x][j], g[y][j]) - min(f[x][j], f[y][j]) + 1 >= n) {
        continue;
      }
      int nx = qryf(f[x][j], g[y][j]);
      int ny = qryg(f[x][j], g[y][j]);
      x = nx;
      y = ny;
      ans |= (1 << j);
    }
    ans++;
    printf("%d ", ans);
  }
  return 0;
}
