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>
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
  int x = 0;
  while ((1U << x) < (unsigned int)(n)) x++;
  return x;
}
int bsf(unsigned int n) { return __builtin_ctz(n); }
}  // namespace internal
}  // namespace atcoder
namespace atcoder {
template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
 public:
  segtree() : segtree(0) {}
  segtree(int n) : segtree(std::vector<S>(n, e())) {}
  segtree(const std::vector<S>& v) : _n(int(v.size())) {
    log = internal::ceil_pow2(_n);
    size = 1 << log;
    d = std::vector<S>(2 * size, e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i >= 1; i--) {
      update(i);
    }
  }
  void set(int p, S x) {
    assert(0 <= p && p < _n);
    p += size;
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  S get(int p) {
    assert(0 <= p && p < _n);
    return d[p + size];
  }
  S prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    S sml = e(), smr = e();
    l += size;
    r += size;
    while (l < r) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
      l >>= 1;
      r >>= 1;
    }
    return op(sml, smr);
  }
  S all_prod() { return d[1]; }
  template <bool (*f)(S)>
  int max_right(int l) {
    return max_right(l, [](S x) { return f(x); });
  }
  template <class F>
  int max_right(int l, F f) {
    assert(0 <= l && l <= _n);
    assert(f(e()));
    if (l == _n) return _n;
    l += size;
    S sm = e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!f(op(sm, d[l]))) {
        while (l < size) {
          l = (2 * l);
          if (f(op(sm, d[l]))) {
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - size;
      }
      sm = op(sm, d[l]);
      l++;
    } while ((l & -l) != l);
    return _n;
  }
  template <bool (*f)(S)>
  int min_left(int r) {
    return min_left(r, [](S x) { return f(x); });
  }
  template <class F>
  int min_left(int r, F f) {
    assert(0 <= r && r <= _n);
    assert(f(e()));
    if (r == 0) return 0;
    r += size;
    S sm = e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!f(op(d[r], sm))) {
        while (r < size) {
          r = (2 * r + 1);
          if (f(op(d[r], sm))) {
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - size;
      }
      sm = op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

 private:
  int _n, size, log;
  std::vector<S> d;
  void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
}  // namespace atcoder
using namespace std;
int opmax(int a, int b) { return a < b ? b : a; }
int opmin(int a, int b) { return a < b ? a : b; }
int emax() { return -(1 << 20); }
int emin() { return 1 << 20; }
int N;
int A[1 << 17];
int L[18][1 << 17], R[18][1 << 17];
int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    L[0][i] = R[0][i] = A[i];
  }
  if (N == 1) {
    puts("0");
    return 0;
  }
  vector<atcoder::segtree<int, opmax, emax> > RQ;
  vector<atcoder::segtree<int, opmin, emin> > LQ;
  for (int k = 0; k < 18; k++) {
    if (k > 0) {
      for (int i = 0; i < N; i++) {
        L[k][i] = L[k - 1][i];
        R[k][i] = R[k - 1][i];
        if (L[k - 1][i] + R[k - 1][i] + 1 >= N) continue;
        int l = i - L[k - 1][i], r = i + R[k - 1][i];
        int nl, nr;
        if (l < 0) {
          nl = opmin(LQ.back().prod(0, r + 1), LQ.back().prod(N + l, N) - N);
          nr = opmax(RQ.back().prod(0, r + 1), RQ.back().prod(N + l, N) - N);
        } else if (r >= N) {
          nl = opmin(LQ.back().prod(l, N), LQ.back().prod(0, r + 1 - N) + N);
          nr = opmax(RQ.back().prod(l, N), RQ.back().prod(0, r + 1 - N) + N);
        } else {
          nl = LQ.back().prod(l, r + 1);
          nr = RQ.back().prod(l, r + 1);
        }
        L[k][i] = i - nl;
        R[k][i] = nr - i;
      }
    }
    vector<int> Ri(N), Li(N);
    for (int i = 0; i < N; i++) {
      if (L[k][i] + R[k][i] + 1 >= N) L[k][i] = R[k][i] = 5 * N;
      Li[i] = i - L[k][i];
      Ri[i] = i + R[k][i];
    }
    RQ.emplace_back(Ri);
    LQ.emplace_back(Li);
  }
  for (int i = 0; i < N; i++) {
    int ans = 0;
    int l = i, r = i;
    for (int k = 18; k--;) {
      int nl, nr;
      if (l < 0) {
        nl = opmin(LQ[k].prod(0, r + 1), LQ[k].prod(N + l, N) - N);
        nr = opmax(RQ[k].prod(0, r + 1), RQ[k].prod(N + l, N) - N);
      } else if (r >= N) {
        nl = opmin(LQ[k].prod(l, N), LQ[k].prod(0, r + 1 - N) + N);
        nr = opmax(RQ[k].prod(l, N), RQ[k].prod(0, r + 1 - N) + N);
      } else {
        nl = LQ[k].prod(l, r + 1);
        nr = RQ[k].prod(l, r + 1);
      }
      if ((i - nl) + (nr - i) + 1 < N) {
        l = nl, r = nr;
        ans |= 1 << k;
      }
    }
    printf("%d%c", ans + 1, i + 1 == N ? 10 : 32);
  }
}
