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 = 200005, L = 262144, G = 18, inf = 1e9;
int n, a[N], ans[N];
struct segtree {
  int v[2 * L];
  void upd(int P, int V) {
    P += L;
    v[P] = V;
    P /= 2;
    while (P) {
      v[P] = max(v[2 * P], v[2 * P + 1]);
      P /= 2;
    }
  }
  int get(int S, int E) {
    S += L;
    E += L;
    int R = -inf;
    while (S <= E) {
      if (S % 2 == 1) {
        R = max(R, v[S]);
        S++;
      }
      if (E % 2 == 0) {
        R = max(R, v[E]);
        E--;
      }
      S /= 2;
      E /= 2;
    }
    return R;
  }
} s[G], e[G];
int main() {
  scanf("%d", &n);
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[i + n] = a[i];
  }
  n *= 2;
  for (int i = 1; i <= n; i++) {
    s[0].upd(i, -max(1, i - a[i]));
    e[0].upd(i, min(n, i + a[i]));
  }
  for (int i = 1; i < G; i++) {
    for (int j = 1; j <= n; j++) {
      int A = max(1, -s[i - 1].get(j, j)), B = min(n, e[i - 1].get(j, j));
      s[i].upd(j, s[i - 1].get(A, B));
      e[i].upd(j, e[i - 1].get(A, B));
    }
  }
  for (int i = 1; i <= n / 2; i++) {
    ans[i] = inf;
  }
  for (int i = 1; i <= n; i++) {
    int X = 0, A = i, B = i;
    for (int j = G; j--;) {
      int NA = -s[j].get(A, B), NB = e[j].get(A, B);
      if (NB - NA + 1 < n / 2) {
        X += (1 << j);
        A = NA;
        B = NB;
      }
    }
    int I = i > n / 2 ? i - n / 2 : i;
    ans[I] = min(ans[I], X + 1);
  }
  for (int i = 1; i <= n / 2; i++) {
    printf("%d ", ans[i]);
  }
}
