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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const int inf = numeric_limits<int>::max() / 2;
const long double eps = 1e-9;
const long double pi = acosl(-1);
template <typename T>
inline bool mineq(T& a, T b) {
  return (a > b) ? (a = b, 1) : 0;
}
template <typename T>
inline bool maxeq(T& a, T b) {
  return (a < b) ? (a = b, 1) : 0;
}
inline void solve(), read();
const string file = "";
signed main() {
  if (file != "") {
    freopen((file + ".in").c_str(), "r", stdin);
    freopen((file + ".out").c_str(), "w", stdout);
  }
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  read();
  solve();
  return 0;
}
struct vertex {
  int minn = inf, maxx = -inf;
};
struct segment {
  int n;
  vector<vertex> t;
  segment() {}
  segment(int n_) {
    int LOG = log2(n_) + 1;
    n = 1ll << LOG;
    t.resize(2 * n);
  }
  vertex merge(vertex v1, vertex v2) {
    vertex v;
    v.minn = min(v1.minn, v2.minn);
    v.maxx = max(v1.maxx, v2.maxx);
    return v;
  }
  void upd(int v, int minn, int maxx) {
    v += n;
    t[v].minn = minn;
    t[v].maxx = maxx;
    v /= 2;
    while (v >= 1) {
      t[v] = merge(t[2 * v], t[2 * v + 1]);
      v /= 2;
    }
  }
  vertex get(int v, int tl, int tr, int l, int r) {
    if (tl > r || tr < l) {
      return {};
    }
    if (l <= tl && tr <= r) {
      return t[v];
    }
    int tm = (tl + tr) / 2;
    vertex v1 = get(2 * v, tl, tm, l, r);
    vertex v2 = get(2 * v + 1, tm + 1, tr, l, r);
    return merge(v1, v2);
  }
  inline vertex get(int i) { return t[n + i]; }
};
const int LOG = 17;
segment st[LOG];
int n;
vector<int> a;
inline void solve() {
  if (n == 1) {
    cout << 0 << "\n";
    return;
  }
  for (int i = 0; i < LOG; i++) {
    st[i] = segment(3 * n);
  }
  for (int i = 0; i < 3 * n; i++) {
    int minn = max(i - a[i], 0);
    int maxx = min(i + a[i], 3 * n);
    st[0].upd(i, minn, maxx);
  }
  for (int k = 1; k < LOG; k++) {
    for (int i = 0; i < 3 * n; i++) {
      vertex v = st[k - 1].get(i);
      vertex nv = st[k - 1].get(1, 0, st[k - 1].n - 1, v.minn, v.maxx);
      st[k].upd(i, nv.minn, nv.maxx);
    }
  }
  for (int i = n; i < 2 * n; i++) {
    int ans = 0;
    int l = i, r = i;
    for (int k = LOG - 1; k >= 0; k--) {
      vertex v = st[k].get(1, 0, st[k].n - 1, l, r);
      if (v.maxx - v.minn + 1 <= n) {
        l = v.minn, r = v.maxx;
        ans += (1ll << k);
      }
    }
    if (r - l + 1 < n) {
      ++ans;
    }
    cout << ans << " ";
  }
}
inline void read() {
  cin >> n;
  a.resize(3 * n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[n + i] = a[2 * n + i] = a[i];
  }
}
