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;
inline int readChar();
template <class T = int>
inline T readInt();
template <class T>
inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeWord(const char *s);
static const int buf_size = 4096;
inline int getChar() {
  static char buf[buf_size];
  static int len = 0, pos = 0;
  if (pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
  if (pos == len) return -1;
  return buf[pos++];
}
inline int readChar() {
  int c = getChar();
  while (c <= 32) c = getChar();
  return c;
}
template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T x = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return s == 1 ? x : -x;
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x) {
  if (write_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end) {
  if (x < 0) writeChar('-'), x = -x;
  char s[24];
  int n = 0;
  while (x || !n) s[n++] = '0' + x % 10, x /= 10;
  while (n--) writeChar(s[n]);
  if (end) writeChar(end);
}
inline void writeWord(const char *s) {
  while (*s) writeChar(*s++);
}
struct Flusher {
  ~Flusher() {
    if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  }
} flusher;
inline void readWord(char *s) {
  int c = readChar();
  while (c > 32) *s++ = c, c = getChar();
  *s = 0;
}
inline void writeDouble(double x, int output_len) {
  if (x < 0) writeChar('-'), x = -x;
  int t = (int)x;
  writeInt(t), x -= t;
  writeChar('.');
  for (int i = output_len - 1; i > 0; i--) {
    x *= 10;
    t = min(9, (int)x);
    writeChar('0' + t), x -= t;
  }
  x *= 10;
  t = min(9, (int)(x + 0.5));
  writeChar('0' + t);
}
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
using ull = unsigned long long;
using pnt = complex<ld>;
istream &operator>>(istream &in, pnt &p) {
  ld a, b;
  in >> a >> b;
  p = {a, b};
  return in;
}
ld crs(pnt a, pnt b) { return a.real() * b.imag() - a.imag() * b.real(); }
const int M = 998244353;
const int mod = 1e9 + 7;
const int inf = 1e9 + 100;
const ll inf64 = 1e18L;
const ld pi = acos(-1.0L);
const ld eps = 1e-5L;
const int di[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dj[] = {2, -2, 2, -2, 1, -1, 1, -1};
const int dii[] = {0, 1, -1, 0};
const int djj[] = {1, 0, 0, -1};
const int dx[] = {1, 1, -1, -1};
const int dy[] = {1, -1, 1, -1};
const int SQ = 1000;
const int nax = 3e5 + 1;
const int LG = 20;
struct segTree {
  int n;
  vector<pii> t;
  segTree(int n) : n(n), t(2 * n, make_pair(inf, -inf)) {}
  pii comb(pii a, pii b) {
    return make_pair(min(a.first, b.first), max(a.second, b.second));
  }
  void upd(int v, pii x) {
    t[v += n] = x;
    for (v >>= 1; v; v >>= 1) t[v] = comb(t[v * 2], t[v * 2 + 1]);
  }
  pii get(int l, int r) {
    pii ret = make_pair(inf, -inf);
    for (l += n, r += n; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
      if (l & 1) ret = comb(ret, t[l]);
      if (!(r & 1)) ret = comb(ret, t[r]);
    }
    return ret;
  }
};
int pw[LG + 1];
int n, a[nax];
int la[nax], ra[nax];
int lup[LG][nax], rup[LG][nax];
vector<segTree> t;
inline bool ok(int pos, int rem) {
  int L = pos, R = pos;
  for (int i = LG - 1; i >= 0; i--) {
    if (pw[i] <= rem) {
      pii q = t[i].get(L, R);
      L = q.first;
      R = q.second;
      rem -= pw[i];
    }
  }
  return R - L + 1 >= n;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout.precision(10);
  cout << fixed;
  pw[0] = 1;
  for (int i = 1; i < LG + 1; i++) pw[i] = 2 * pw[i - 1];
  cin >> n;
  if (n == 1) return cout << 0, 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    la[i] = max(0, i - a[i]);
    la[i + n] = i + n - a[i];
    la[i + 2 * n] = i + 2 * n - a[i];
    ra[i] = i + a[i];
    ra[i + n] = i + n + a[i];
    ra[i + 2 * n] = min(3 * n - 1, i + 2 * n + a[i]);
  }
  for (int i = 0; i < LG; i++) t.emplace_back(segTree(3 * n));
  for (int i = 0; i < 3 * n; i++) t[0].upd(i, make_pair(la[i], ra[i]));
  for (int i = 0; i < 3 * n; i++) {
    lup[0][i] = la[i];
    rup[0][i] = ra[i];
  }
  for (int j = 1; j < LG; j++) {
    for (int i = 0; i < 3 * n; i++) {
      pii q = t[j - 1].get(lup[j - 1][i], rup[j - 1][i]);
      lup[j][i] = q.first;
      rup[j][i] = q.second;
      t[j].upd(i, q);
    }
  }
  for (int i = 0; i < n; i++) {
    int pos = i + n;
    int lf = 1, rg = n;
    while (lf < rg) {
      int md = (lf + rg) >> 1;
      if (ok(pos, md))
        rg = md;
      else
        lf = md + 1;
    }
    cout << lf << ' ';
  }
}
