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 <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 998244353) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 998244353) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
const int MN = (1 << 20) + 5;
struct mb {
  int M, T[MN];
  void init(int sz) {
    for (M = 1; sz + 2 > M; M <<= 1)
      ;
  }
  void init(int sz, int val) {
    for (M = 1; sz + 2 > M; M <<= 1)
      ;
    for (int(i) = 0; (i) < (int)(MN); (i)++) T[i] = val;
  }
  void clear() { memset(T, 0, sizeof T); }
  void uptSingleMax(int l, int val) {
    l += M;
    T[l] = val;
    while (l > 1) {
      T[l >> 1] = max(T[l], T[l ^ 1]);
      l >>= 1;
    }
  }
  void uptSingleMin(int l, int val) {
    l += M;
    T[l] = val;
    while (l > 1) {
      T[l >> 1] = min(T[l], T[l ^ 1]);
      l >>= 1;
    }
  }
  int qyRangeMax(int l, int r) {
    int ans = 0;
    for (l = l + M - 1, r = r + M + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (~l & 1) ans = max(ans, T[l ^ 1]);
      if (r & 1) ans = max(ans, T[r ^ 1]);
    }
    return ans;
  }
  int qyRangeMin(int l, int r) {
    int ans = (1 << 30);
    for (l = l + M - 1, r = r + M + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (~l & 1) ans = min(ans, T[l ^ 1]);
      if (r & 1) ans = min(ans, T[r ^ 1]);
    }
    return ans;
  }
} l[20], r[20];
int a[300105], N;
void fmain(int ID) {
  scanf("%d", &n);
  if (n == 1) {
    puts("0");
    return;
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    scanf("%d", a + i);
    a[n + n + i] = a[n + i] = a[i];
  }
  N = n * 3;
  for (int(i) = 0; (i) < (int)(20); (i)++) {
    l[i].init(N, (1000000000));
    r[i].init(N, 0);
  }
  for (int(i) = 1; (i) <= (int)(N); (i)++) {
    l[0].uptSingleMin(i, max(i - a[i], 1));
    r[0].uptSingleMax(i, min(i + a[i], N));
  }
  for (int(j) = 1; (j) <= (int)(19); (j)++) {
    for (int(i) = 1; (i) <= (int)(N); (i)++) {
      int L = l[j - 1].qyRangeMin(i, i), R = r[j - 1].qyRangeMax(i, i);
      int tl = l[j - 1].qyRangeMin(L, R);
      int tr = r[j - 1].qyRangeMax(L, R);
      l[j].uptSingleMin(i, tl);
      r[j].uptSingleMax(i, tr);
    }
  }
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    int L = n + i, R = n + i;
    int ans = (1 << 30), cur = 0;
    for (int j = 19; ~j; j--) {
      int tl = l[j].qyRangeMin(L, R);
      int tr = r[j].qyRangeMax(L, R);
      if (tr - tl >= n - 1) {
        mintt(ans, cur + (1 << j));
      } else {
        L = tl;
        R = tr;
        cur += 1 << j;
      }
    }
    printf("%d ", ans);
  }
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
