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;
template <class T>
inline void read(T &x) {
  char ch = getchar();
  int op = 0;
  x = 0;
  while (!isdigit(ch)) op |= (ch == '-'), ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  if (op) x = -x;
}
const int N = 300005;
int x[N], l[20][N], r[20][N];
int n, m;
struct ST {
  int mn[N << 2], mx[N << 2];
  void build(int o, int l, int r, int L[N], int R[N]) {
    if (l == r) {
      mn[o] = L[l], mx[o] = R[l];
      return;
    }
    build((o << 1), l, ((l + r) >> 1), L, R);
    build((o << 1 | 1), ((l + r) >> 1) + 1, r, L, R);
    mn[o] = min(mn[(o << 1)], mn[(o << 1 | 1)]);
    mx[o] = max(mx[(o << 1)], mx[(o << 1 | 1)]);
  }
  int qmin(int o, int l, int r, int x, int y) {
    if (l == x && y == r) return mn[o];
    if (y <= ((l + r) >> 1)) return qmin((o << 1), l, ((l + r) >> 1), x, y);
    if (((l + r) >> 1) < x)
      return qmin((o << 1 | 1), ((l + r) >> 1) + 1, r, x, y);
    return min(
        qmin((o << 1), l, ((l + r) >> 1), x, ((l + r) >> 1)),
        qmin((o << 1 | 1), ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, y));
  }
  int qmax(int o, int l, int r, int x, int y) {
    if (l == x && y == r) return mx[o];
    if (y <= ((l + r) >> 1)) return qmax((o << 1), l, ((l + r) >> 1), x, y);
    if (((l + r) >> 1) < x)
      return qmax((o << 1 | 1), ((l + r) >> 1) + 1, r, x, y);
    return max(
        qmax((o << 1), l, ((l + r) >> 1), x, ((l + r) >> 1)),
        qmax((o << 1 | 1), ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, y));
  }
} T[20];
void doit(int s) {
  int l = s, r = s, res = 0, L, R;
  for (int i = (18); i >= (0); i--) {
    L = T[i].qmin(1, 1, m, l, r);
    R = T[i].qmax(1, 1, m, l, r);
    if (R - L + 1 < n) {
      l = L, r = R;
      res |= 1 << i;
    }
  }
  printf("%d ", res + 1);
}
int main() {
  read(n);
  if (n == 1) return puts("0"), 0;
  for (int i = (1); i <= (n); i++) {
    read(x[i]);
    x[i + n] = x[i + n + n] = x[i];
  }
  m = 3 * n;
  for (int i = (1); i <= (m); i++) {
    l[0][i] = max(1, i - x[i]);
    r[0][i] = min(m, i + x[i]);
  }
  T[0].build(1, 1, m, l[0], r[0]);
  for (int j = (1); j <= (18); j++) {
    for (int i = (1); i <= (m); i++) {
      l[j][i] = T[j - 1].qmin(1, 1, m, l[j - 1][i], r[j - 1][i]);
      r[j][i] = T[j - 1].qmax(1, 1, m, l[j - 1][i], r[j - 1][i]);
    }
    T[j].build(1, 1, m, l[j], r[j]);
  }
  for (int i = (n + 1); i <= (n + n); i++) doit(i);
  return 0;
}
