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;
const int LOG = 15;
const int MAX = 524288;
struct Tree {
  array<int, 2 * MAX> arr;
  function<int(int, int)> op;
  void Fill(int val) { fill(arr.begin(), arr.end(), val); }
  void SetOp(function<int(int, int)> _op) { op = _op; }
  void Add(int pos, int how) { arr[pos + MAX] = how; }
  void Rebuild() {
    for (int i = MAX - 1; i > 0; --i) arr[i] = op(arr[2 * i], arr[2 * i + 1]);
  }
  int Get(int l, int r) {
    l += MAX, r += MAX;
    int res = op(arr[l], arr[r]);
    while (l != r) {
      int pl = l >> 1;
      int pr = r >> 1;
      if (pl == pr) break;
      if (2 * pl == l) res = op(res, arr[l + 1]);
      if (2 * pr + 1 == r) res = op(res, arr[r - 1]);
      l = pl;
      r = pr;
    }
    return res;
  }
};
int n;
vector<int> in;
Tree jl[LOG + 1], jr[LOG + 1];
void Init() {
  jl[0].SetOp([](int a, int b) { return min(a, b); });
  jr[0].SetOp([](int a, int b) { return max(a, b); });
  jl[0].Fill(1E9);
  jr[0].Fill(-1E9);
  for (int i = 0; i < ((int)(in).size()); ++i) {
    jl[0].Add(i, max(0, i - in[i]));
    jr[0].Add(i, min(((int)(in).size()) - 1, i + in[i]));
  }
  jl[0].Rebuild();
  jr[0].Rebuild();
  for (int l = 1; l <= LOG; ++l) {
    jl[l].SetOp([](int a, int b) { return min(a, b); });
    jr[l].SetOp([](int a, int b) { return max(a, b); });
    jl[l].Fill(1E9);
    jr[l].Fill(-1E9);
    for (int i = 0; i < ((int)(in).size()); ++i) {
      int le = jl[l - 1].Get(i, i);
      int ri = jr[l - 1].Get(i, i);
      jl[l].Add(i, jl[l - 1].Get(le, ri));
      jr[l].Add(i, jr[l - 1].Get(le, ri));
    }
    jl[l].Rebuild();
    jr[l].Rebuild();
  }
}
bool Ok(int pos, int len) {
  int le = pos + n, ri = pos + n;
  int how = LOG;
  while (len > 0) {
    if ((1 << how) > len)
      --how;
    else {
      len -= (1 << how);
      int nle = jl[how].Get(le, ri);
      int nri = jr[how].Get(le, ri);
      le = nle;
      ri = nri;
      if (ri - le + 1 >= n) return true;
    }
  }
  return ri - le + 1 >= n;
}
int Solve(int pos) {
  int lo = 0, hi = 1;
  while (!Ok(pos, hi)) lo = hi, hi = min(n + 1, hi << 1);
  for (;;) {
    if (lo + 1 >= hi) {
      if (Ok(pos, lo))
        return lo;
      else
        return hi;
    }
    int mid = (lo + hi) >> 1;
    if (Ok(pos, mid))
      hi = mid;
    else
      lo = mid;
  }
}
int main() {
  scanf("%d", &n);
  in.resize(n);
  for (int& e : in) scanf("%d", &e);
  in.resize(3 * n);
  for (int i = 0; i < n; ++i) in[i + n] = in[i], in[i + 2 * n] = in[i];
  Init();
  for (int i = 0; i < n; ++i) {
    printf("%d%c", Solve(i), (i + 1 == n ? '\n' : ' '));
  }
  return 0;
}
