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 GCC optimize("O3")
using namespace std;
const long long mod7 = 1000000007LL;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y, long long _mod = mod7) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y, long long _mod = mod7) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y, long long _mod = mod7) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1ll;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0ll;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
void sleep(double sec = 1021) {
  clock_t s = clock();
  while (clock() - s < CLOCKS_PER_SEC * sec)
    ;
}
int __ = 1, _cs;
int n;
int a[300001];
int l[18][300001], r[18][300001];
int mini[18][1048576], maxi[18][1048576];
bool out;
inline void build(int t, int id, int cl, int cr) {
  if (cl == cr) {
    mini[t][id] = l[t][cl];
    maxi[t][id] = r[t][cr];
    return;
  }
  int mid = (cl + cr) / 2;
  build(t, id * 2, cl, mid);
  build(t, id * 2 + 1, mid + 1, cr);
  mini[t][id] = min(mini[t][id * 2], mini[t][id * 2 + 1]);
  maxi[t][id] = max(maxi[t][id * 2], maxi[t][id * 2 + 1]);
}
inline int qmin(int t, int id, int cl, int cr, int ql, int qr) {
  if (cl > qr || ql > cr) return 1e9;
  if (ql <= cl && cr <= qr) return mini[t][id];
  int mid = (cl + cr) / 2;
  return min(qmin(t, id * 2, cl, mid, ql, qr),
             qmin(t, id * 2 + 1, mid + 1, cr, ql, qr));
}
inline int qmax(int t, int id, int cl, int cr, int ql, int qr) {
  if (cl > qr || ql > cr) return 0;
  if (ql <= cl && cr <= qr) return maxi[t][id];
  int mid = (cl + cr) / 2;
  return max(qmax(t, id * 2, cl, mid, ql, qr),
             qmax(t, id * 2 + 1, mid + 1, cr, ql, qr));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  if (n == 1) {
    cout << 0 << endl;
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= 3 * n; i++) {
    int cur = (i - 1) % n + 1;
    l[0][i] = max(1, i - a[cur]);
    r[0][i] = min(3 * n, i + a[cur]);
  }
  for (int j = 1; j <= 17; j++) {
    build(j - 1, 1, 1, 3 * n);
    for (int i = 1; i <= 3 * n; i++) {
      l[j][i] = max(1, qmin(j - 1, 1, 1, 3 * n, l[j - 1][i], r[j - 1][i]));
      r[j][i] = min(3 * n, qmax(j - 1, 1, 1, 3 * n, l[j - 1][i], r[j - 1][i]));
    }
  }
  for (int i = 1; i <= n; i++) {
    int cl = i + n, cr = i + n, ans = 0;
    for (int j = 16; j >= 0; j--) {
      int nl = max(1, qmin(j, 1, 1, 3 * n, cl, cr));
      int nr = min(3 * n, qmax(j, 1, 1, 3 * n, cl, cr));
      if (nr - nl < n - 1) {
        ans |= (1 << j);
        cl = nl;
        cr = nr;
      }
    }
    cout << ans + 1 << ' ';
  }
  cout << endl;
}
