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;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
const int MAXLG = 16;
struct Range {
  int l, r;
  Range() {}
  Range(int l, int r) : l(l), r(r) {}
};
struct RMQ {
  int n, lgn;
  vector<int> a;
  vector<vector<int>> b;
  vector<int> lg;
  void init(int _n) {
    n = _n;
    a = vector<int>(n, 0);
  }
  void build() {
    lg = vector<int>(n + 1);
    lg[1] = 0;
    for (int i = (1); i <= (n); ++i) {
      lg[i] = lg[i - 1];
      while ((2 << lg[i]) <= i) ++lg[i];
    }
    lgn = lg[n];
    b = vector<vector<int>>(n, vector<int>(lgn + 1, -1));
    for (int i = (0); i < (n); ++i) b[i][0] = i;
    for (int k = (0); k < (lgn); ++k)
      for (int i = (0); i < (n); ++i) {
        b[i][k + 1] = b[i][k];
        if (i + (1 << k) < n && a[b[i + (1 << k)][k]] < a[b[i][k]])
          b[i][k + 1] = b[i + (1 << k)][k];
      }
  }
  int get(int l, int r) {
    int k = lg[r - l + 1];
    return a[b[l][k]] < a[b[r - (1 << k) + 1][k]] ? b[l][k]
                                                  : b[r - (1 << k) + 1][k];
  }
};
int n;
int a[MAXN];
int ans[MAXN];
Range range[MAXN][MAXLG + 1];
RMQ lrmq, rrmq;
Range normalize(const Range &cur) {
  if (cur.l < 0) return Range(cur.l + n, cur.r);
  if (cur.r >= n) return Range(cur.l, cur.r - n);
  return cur;
}
Range merge(const Range &a, const Range &b) {
  if (a.l > b.l) return merge(b, a);
  if (a.l > a.r) {
    if (b.l <= b.r)
      return Range(a.l, a.r);
    else if (b.r < a.l)
      return Range(a.l, max(a.r, b.r));
    else
      return Range(0, n - 1);
  } else if (b.l <= a.r) {
    if (b.l <= b.r)
      return Range(a.l, max(a.r, b.r));
    else if (b.r < a.l)
      return Range(a.l, b.r);
    else
      return Range(0, n - 1);
  } else {
    assert(b.r < b.l && b.r >= a.l);
    return Range(b.l, max(a.r, b.r));
  }
}
int getlft(const Range &cur) {
  int l = cur.l, r = cur.r;
  if (r < l) r += n;
  return lrmq.get(l, r) % n;
}
int getrgt(const Range &cur) {
  int l = cur.l, r = cur.r;
  if (r < l) r += n;
  return rrmq.get(l, r) % n;
}
int getlen(const Range &cur) {
  int l = cur.l, r = cur.r;
  if (r < l) r += n;
  return r - l + 1;
}
Range extend(const Range &cur, int k) {
  int l = getlft(cur), r = getrgt(cur);
  return merge(merge(range[l][k], cur), range[r][k]);
}
int calc(int start, int steps) {
  Range cur(start, start);
  for (int k = (0); k <= (MAXLG); ++k)
    if (steps & (1 << k)) cur = extend(cur, k);
  return getlen(cur);
}
void solve() {
  for (int i = (0); i < (n); ++i) a[i] = min(a[i], n - 1);
  lrmq.init(2 * n);
  for (int i = (0); i < (2 * n); ++i) lrmq.a[i] = i - a[i % n];
  lrmq.build();
  rrmq.init(2 * n);
  for (int i = (0); i < (2 * n); ++i) rrmq.a[i] = -(i + a[i % n]);
  rrmq.build();
  for (int i = (0); i < (n); ++i)
    range[i][0] =
        merge(normalize(Range(i - a[i], i)), normalize(Range(i, i + a[i])));
  for (int k = (0); k < (MAXLG); ++k)
    for (int i = (0); i < (n); ++i) range[i][k + 1] = extend(range[i][k], k);
  for (int i = (0); i < (n); ++i) {
    int lo = -1, hi = n;
    while (lo + 1 < hi) {
      int mi = lo + (hi - lo) / 2;
      if (calc(i, mi) >= n)
        hi = mi;
      else
        lo = mi;
    }
    ans[i] = hi;
  }
}
void run() {
  scanf("%d", &n);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]);
  solve();
  for (int i = (0); i < (n); ++i) {
    if (i != 0) printf(" ");
    printf("%d", ans[i]);
  }
  puts("");
}
int bfans[MAXN];
void bfsolve() {
  for (int i = (0); i < (n); ++i) {
    int l = i, r = i, cur = 0;
    while (true) {
      int cnt = l <= r ? r - l + 1 : n - r + l + 1;
      if (cnt == n) break;
      int lidx = l, ridx = l;
      for (int at = l;; ++at) {
        if (at - a[at % n] < lidx - a[lidx % n]) lidx = at;
        if (at + a[at % n] > ridx + a[ridx % n]) ridx = at;
        if (at % n == r) break;
      }
      int ncnt = ridx - lidx + 1 + a[lidx % n] + a[ridx % n];
      if (cur > n) exit(0);
      ++cur;
      if (ncnt >= n) break;
      l = lidx - a[lidx % n];
      while (l < 0) l += n;
      r = ridx + a[ridx % n];
      while (r >= n) r -= n;
    }
    bfans[i] = cur;
  }
}
void stress() {
  for (int rep = (0); rep < (100000); ++rep) {
    n = rand() % 20;
    for (int i = (0); i < (n); ++i) a[i] = rand() % 10 + 1;
    solve();
    bfsolve();
    bool ok = true;
    for (int i = (0); i < (n); ++i)
      if (ans[i] != bfans[i]) ok = false;
    if (ok) {
      printf(".");
      continue;
    }
    printf("err (rep=%d)\n", rep);
    printf("%d\n", n);
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", a[i]);
    }
    puts("");
    printf("have:");
    for (int i = (0); i < (n); ++i) printf(" %d", ans[i]);
    puts("");
    printf("want:");
    for (int i = (0); i < (n); ++i) printf(" %d", bfans[i]);
    puts("");
    break;
  }
}
int main() {
  run();
  return 0;
}
