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 std::abs;
using std::bitset;
using std::cerr;
using std::cin;
using std::cout;
using std::map;
using std::max;
using std::min;
using std::pair;
using std::set;
using std::sort;
using std::string;
using std::swap;
using std::unordered_map;
using std::unordered_set;
using std::vector;
using ll = long long;
using uint = unsigned int;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;
using ld = long double;
using vci = vector<int>;
using vcl = vector<ll>;
template <typename T>
void _dbg(const char* _s, T _h) {
  cerr << _s << " = " << _h << "\n";
}
template <typename T, typename... Ts>
void _dbg(const char* _s, T _h, Ts... _t) {
  int _b = 0;
  while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',') cerr << *_s++;
  cerr << " = " << _h << ",";
  _dbg(_s + 1, _t...);
}
struct init {
  init() {
    cin.tie(0);
    std::iostream::sync_with_stdio(0);
    cout << std::fixed << std::setprecision(10);
    cerr << std::fixed << std::setprecision(5);
  }
  ~init() {}
} init;
template <typename T, typename U>
void upx(T& x, U y) {
  if (x < y) x = y;
}
template <typename T, typename U>
void upn(T& x, U y) {
  if (x > y) x = y;
}
const int N = 3e5 + 35, L = 20, OO = 1e9;
int a[N];
int second, n;
struct seg {
  vector<int> tn, tx;
  void build() {
    for (int i = second - 1; i > 0; --i) {
      tn[i] = min(tn[i + i], tn[i + i + 1]);
      tx[i] = max(tx[i + i], tx[i + i + 1]);
    }
  }
  int getmin(int l, int r) {
    upx(l, 0);
    upn(r, 3 * n - 1);
    int res = OO;
    for (l += second, r += second + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) upn(res, tn[l++]);
      if (r & 1) upn(res, tn[--r]);
    }
    return max(0, res);
  }
  int getmax(int l, int r) {
    upx(l, 0);
    upn(r, 3 * n - 1);
    int res = -OO;
    for (l += second, r += second + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) upx(res, tx[l++]);
      if (r & 1) upx(res, tx[--r]);
    }
    return min(res, 3 * n - 1);
  }
} st[L];
int32_t main() {
  cin >> n;
  if (n == 1) {
    cout << "0\n";
    return n - 1;
  }
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i + n] = a[i];
    a[i + n + n] = a[i];
  }
  second = 1;
  while (second < 3 * n) second *= 2;
  for (int j = 0; j < L; ++j) {
    st[j].tn.resize(second + second);
    st[j].tx.resize(second + second);
  }
  for (int i = second; i < second + 3 * n; ++i) {
    st[0].tn[i] = (i - second) - a[i - second];
    st[0].tx[i] = (i - second) + a[i - second];
  }
  st[0].build();
  for (int j = 1; j < L; ++j) {
    for (int i = 0; i < n * 3; ++i) {
      int ls = st[j - 1].getmin(i, i);
      int rs = st[j - 1].getmax(i, i);
      st[j].tn[i + second] = st[j - 1].getmin(ls, rs);
      st[j].tx[i + second] = st[j - 1].getmax(ls, rs);
    }
    st[j].build();
  }
  for (int i = n; i < 2 * n; ++i) {
    int ans = 0;
    int wl = i, wr = i;
    for (int j = L - 1; j >= 0; --j) {
      int nl = st[j].getmin(wl, wr);
      int nr = st[j].getmax(wl, wr);
      if (nr - nl + 1 < n) {
        wl = nl, wr = nr;
        ans += 1 << j;
      }
    }
    cout << ans + 1 << ' ';
  }
  cout << '\n';
  return 0;
}
