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;
long long gcd(long long a, long long b) {
  if (a == 0LL) return b;
  if (b == 0LL) return a;
  return gcd(b, a % b);
}
const int N = 300005;
const int M = 19;
int A[N];
pair<int, int> tree[M][N << 2];
int n;
pair<int, int> queryTree(int idx, int node, int l, int r, int a, int b) {
  if (l == a && r == b) return tree[idx][node];
  int mid = (l + r) >> 1;
  int left = node << 1;
  int right = left + 1;
  if (b <= mid)
    return queryTree(idx, left, l, mid, a, b);
  else if (a > mid)
    return queryTree(idx, right, mid + 1, r, a, b);
  pair<int, int> L, R;
  L = queryTree(idx, left, l, mid, a, mid);
  R = queryTree(idx, right, mid + 1, r, mid + 1, b);
  L = make_pair(min(L.first, R.first), max(L.second, R.second));
  return L;
}
void build(int idx, int node, int l, int r) {
  if (l == r) {
    if (idx == 0)
      tree[idx][node] = make_pair(max(1, l - A[l]), min(3 * n, l + A[l]));
    else
      tree[idx][node] =
          queryTree(idx - 1, 1, 1, 3 * n, tree[idx - 1][node].first,
                    tree[idx - 1][node].second);
    return;
  }
  int mid = (l + r) >> 1;
  int left = node << 1;
  int right = left + 1;
  build(idx, left, l, mid);
  build(idx, right, mid + 1, r);
  tree[idx][node].first = min(tree[idx][left].first, tree[idx][right].first);
  tree[idx][node].second = max(tree[idx][left].second, tree[idx][right].second);
  return;
}
void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> A[i];
    A[n + i] = A[i];
    A[2 * n + i] = A[i];
  }
  for (int i = 0; i < M; i++) build(i, 1, 1, 3 * n);
  int ans;
  pair<int, int> now, nxt;
  for (int i = n + 1; i <= 2 * n; i++) {
    ans = 0;
    now = make_pair(i, i);
    for (int j = M - 1; j >= 0; j--) {
      nxt = queryTree(j, 1, 1, 3 * n, now.first, now.second);
      if (nxt.second - nxt.first < n - 1) {
        ans += (1 << j);
        now = nxt;
      }
    }
    cout << ans + (now.second - now.first < n - 1) << " ";
  }
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  clock_t clk = clock();
  int t = 1;
  for (int tests = 1; tests <= t; tests++) {
    solve();
  }
  clk = clock() - clk;
  cerr << "Time Elapsed: " << fixed << setprecision(10)
       << ((long double)clk) / CLOCKS_PER_SEC << "\n";
  return 0;
}
