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 MAXN = 300007;
const int LOGN = 20;
pair<int, int> tr[LOGN][MAXN * 4];
pair<int, int> combine(const pair<int, int> &a, const pair<int, int> &b) {
  return pair<int, int>(min(a.first, b.first), max(a.second, b.second));
}
void update(int k, int u, int l, int r, int idx, pair<int, int> p) {
  if (l == r) {
    tr[k][u] = p;
    return;
  }
  int mid = (l + r) / 2;
  if (idx <= mid)
    update(k, u * 2, l, mid, idx, p);
  else
    update(k, u * 2 + 1, mid + 1, r, idx, p);
  tr[k][u] = combine(tr[k][u * 2], tr[k][u * 2 + 1]);
}
pair<int, int> query(int k, int u, int l, int r, int x, int y) {
  if (x <= l && r <= y) return tr[k][u];
  int mid = (l + r) / 2;
  if (mid < x) return query(k, u * 2 + 1, mid + 1, r, x, y);
  if (y <= mid) return query(k, u * 2, l, mid, x, y);
  return combine(query(k, u * 2, l, mid, x, y),
                 query(k, u * 2 + 1, mid + 1, r, x, y));
}
void duipash(vector<int> v, int n) {
  int sz = n + n + n;
  vector<pair<int, int> > tmp;
  for (int i = 0; i < sz; i++) {
    update(0, 1, 0, sz - 1, i,
           pair<int, int>(max(i - v[i], 0), min(i + v[i], sz - 1)));
    tmp.emplace_back(max(i - v[i], 0), min(i + v[i], sz - 1));
  }
  for (int k = 1; (1 << k) < n; k++) {
    for (int i = 0; i < sz; i++) {
      tmp[i] = query(k - 1, 1, 0, sz - 1, tmp[i].first, tmp[i].second);
      update(k, 1, 0, sz - 1, i, tmp[i]);
    }
  }
}
int solve(int n, int idx) {
  int seconds = 0;
  int sz = n + n + n;
  int l = n + idx, r = n + idx;
  for (int k = LOGN - 1; k >= 0; k--) {
    if (n <= (1 << k)) continue;
    pair<int, int> p = query(k, 1, 0, sz - 1, l, r);
    if (p.second - p.first >= n - 1) continue;
    seconds += 1 << k;
    l = p.first;
    r = p.second;
  }
  if (r - l < n - 1) seconds++;
  return seconds;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> v(n + n + n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    v[n + n + i] = v[n + i] = v[i];
  }
  duipash(v, n);
  for (int i = 0; i < n; i++) {
    int ans = solve(n, i);
    cout << ans << " ";
  }
  return 0;
}
