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 RAGETREE_SZ = 1 << 19;
const int RAGETREE_DEP = 17;
pair<int, int> ragetree[RAGETREE_DEP][2 * RAGETREE_SZ];
void fix(int idx) {
  for (int i = RAGETREE_SZ - 1; i > 0; i--) {
    ragetree[idx][i].first =
        min(ragetree[idx][2 * i].first, ragetree[idx][2 * i + 1].first);
    ragetree[idx][i].second =
        max(ragetree[idx][2 * i].second, ragetree[idx][2 * i + 1].second);
  }
}
pair<int, int> qry(int idx, int lhs, int rhs) {
  assert(lhs <= rhs);
  pair<int, int> ret = {2e9, 0};
  lhs += RAGETREE_SZ;
  rhs += RAGETREE_SZ;
  while (lhs <= rhs) {
    if (lhs == rhs) {
      ret.first = min(ret.first, ragetree[idx][lhs].first);
      ret.second = max(ret.second, ragetree[idx][lhs].second);
      break;
    }
    if (lhs % 2) {
      ret.first = min(ret.first, ragetree[idx][lhs].first);
      ret.second = max(ret.second, ragetree[idx][lhs].second);
      lhs++;
    }
    if (rhs % 2 == 0) {
      ret.first = min(ret.first, ragetree[idx][rhs].first);
      ret.second = max(ret.second, ragetree[idx][rhs].second);
      rhs--;
    }
    lhs /= 2;
    rhs /= 2;
  }
  return ret;
}
int l[300005];
int n;
void solve() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> l[i];
    l[i + n] = l[i];
    l[i + 2 * n] = l[i];
  }
  n *= 3;
  for (int d = 0; d < RAGETREE_DEP; d++)
    for (int i = 0; i < RAGETREE_SZ; i++)
      ragetree[d][i + RAGETREE_SZ] = {2e9, 0};
  for (int i = 0; i < n; i++) {
    ragetree[0][i + RAGETREE_SZ] = {max(0, i - l[i]), min(n - 1, i + l[i])};
  }
  for (int d = 1; d < RAGETREE_DEP; d++) {
    fix(d - 1);
    for (int i = 0; i < n; i++) {
      ragetree[d][i + RAGETREE_SZ] =
          qry(d - 1, ragetree[d - 1][i + RAGETREE_SZ].first,
              ragetree[d - 1][i + RAGETREE_SZ].second);
    }
  }
  fflush(stdout);
  cout << flush;
  fix(RAGETREE_DEP - 1);
  n /= 3;
  for (int i = 0; i < n; i++) {
    int lhs = i + n;
    int rhs = i + n;
    int ret = 0;
    for (int d = RAGETREE_DEP - 1; d > 0; d--) {
      pair<int, int> q = qry(d, lhs, rhs);
      if (q.second - q.first + 1 < n) {
        ret += 1 << d;
        lhs = q.first;
        rhs = q.second;
      }
    }
    while (rhs - lhs + 1 < n) {
      pair<int, int> q = qry(0, lhs, rhs);
      ret++;
      lhs = q.first;
      rhs = q.second;
    }
    if (i) cout << " ";
    cout << ret;
  }
  cout << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  solve();
}
