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>
#pragma GCC optimize "-O3"
using namespace std;
const int MAXN = 110000;
const int LOG = 20;
int r[MAXN];
int n;
pair<int, int> up[MAXN][LOG];
pair<int, int> rmq[LOG][MAXN * 4];
void build(int v, int tl, int tr, int k) {
  if (tl + 1 == tr) {
    rmq[k][v] = up[tl][k];
    return;
  }
  int m = (tl + tr) >> 1;
  build(v * 2 + 1, tl, m, k);
  build(v * 2 + 2, m, tr, k);
  rmq[k][v].first = min(rmq[k][v * 2 + 1].first, rmq[k][v * 2 + 2].first);
  rmq[k][v].second = max(rmq[k][v * 2 + 1].second, rmq[k][v * 2 + 2].second);
}
pair<int, int> get(int v, int tl, int tr, int k, int l, int r) {
  if (r <= tl || tr <= l) return make_pair(n, -1);
  if (l <= tl && tr <= r) return rmq[k][v];
  int m = (tl + tr) >> 1;
  auto a = get(v * 2 + 1, tl, m, k, l, r);
  auto b = get(v * 2 + 2, m, tr, k, l, r);
  return {min(a.first, b.first), max(a.second, b.second)};
}
pair<int, int> gget(int l, int r, int x) {
  if (r - l >= n)
    return {0, n};
  else {
    pair<int, int> ans;
    if (l >= 0 && r <= n) {
      ans = get(0, 0, n, x, l, r);
    } else if (l < 0) {
      auto a = get(0, 0, n, x, 0, r);
      auto b = get(0, 0, n, x, l + n, n);
      b.first -= n;
      b.second -= n;
      a.first = min(a.first, b.first);
      a.second = max(a.second, b.second);
      ans = a;
    } else {
      auto a = get(0, 0, n, x, l, n);
      auto b = get(0, 0, n, x, 0, r - n);
      b.first += n;
      b.second += n;
      a.first = min(a.first, b.first);
      a.second = max(a.second, b.second);
      ans = a;
    }
    if (ans.second - ans.first >= n) ans = {0, n};
    return ans;
  }
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n;
  if (n == 1) {
    cout << 0 << "\n";
    return 0;
  }
  for (int i = 0; i < n; ++i) cin >> r[i];
  for (int i = 0; i < n; ++i) {
    up[i][0] = make_pair(i - r[i], i + r[i] + 1);
    if (up[i][0].second - up[i][0].first >= n) up[i][0] = {0, n};
  }
  for (int i = 1; i < LOG; ++i) {
    build(0, 0, n, i - 1);
    for (int j = 0; j < n; ++j) {
      int l = up[j][i - 1].first;
      int r = up[j][i - 1].second;
      up[j][i] = gget(l, r, i - 1);
    }
  }
  build(0, 0, n, LOG - 1);
  for (int i = 0; i < n; ++i) {
    int ans = 0;
    int l = i;
    int r = i + 1;
    for (int j = LOG - 1; j >= 0; --j) {
      int nl, nr;
      tie(nl, nr) = gget(l, r, j);
      if (nl == 0 && nr == n) continue;
      ans += (1 << j);
      l = nl, r = nr;
    }
    cout << ans + 1 << " ";
  }
  cout << "\n";
  return 0;
}
