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")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using db = long double;
using row = vector<int>;
using ii = pair<int, int>;
const int N = 1e5 + 5, A = 6561, LG = 19, MOD = 998244353;
const int SQ = 450;
const long double EPS = 1e-7;
ii tb[19][N + N + N];
int second[N + N + N];
ii qry(int l, int r) {
  int k = second[r - l + 1];
  return ii(min(tb[k][l].first, tb[k][r - (1 << k) + 1].first),
            max(tb[k][l].second, tb[k][r - (1 << k) + 1].second));
}
vector<vector<ii>> buildSparse(vector<int> v) {
  int n = v.size();
  vector<vector<ii>> ret;
  for (int i = 0; i < n + n; i++) {
    v.push_back(v[i]);
  }
  ret.push_back(vector<ii>());
  for (int i = 0; i < n + n + n; i++) {
    ret.back().push_back(ii(max(0, i - v[i]), min(3 * n - 1, i + v[i])));
  }
  for (int j = 1; (1 << j) <= 3 * n; j++) {
    for (int i = 0; i < 3 * n; i++) tb[0][i] = ret.back()[i];
    for (int k = 1; k < 19; k++)
      for (int i = 0; i + (1 << k) <= 3 * n; i++)
        tb[k][i] =
            ii(min(tb[k - 1][i].first, tb[k - 1][i + (1 << (k - 1))].first),
               max(tb[k - 1][i].second, tb[k - 1][i + (1 << (k - 1))].second));
    ret.push_back(vector<ii>(3 * n));
    for (int i = 0; i < 3 * n; i++) {
      ret[j][i] = qry(ret[j - 1][i].first, ret[j - 1][i].second);
    }
  }
  return ret;
}
ii cur[N];
int ans[N];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int k = 2; k < N + N + N; k++) second[k] = second[k >> 1] + 1;
  int n;
  cin >> n;
  if (n == 1) {
    cout << 0 << '\n';
    return 0;
  }
  vector<int> v(n);
  for (auto& x : v) cin >> x;
  auto ST = buildSparse(v);
  for (int i = 0; i < n; i++) cur[i] = ii(i + n, i + n);
  for (int i = ST.size() - 1; i >= 0; --i) {
    for (int j = 0; j < n * 3; j++) tb[0][j] = ST[i][j];
    for (int k = 1; k < 19; k++)
      for (int i = 0; i + (1 << k) <= 3 * n; i++)
        tb[k][i] =
            ii(min(tb[k - 1][i].first, tb[k - 1][i + (1 << (k - 1))].first),
               max(tb[k - 1][i].second, tb[k - 1][i + (1 << (k - 1))].second));
    for (int idx = 0; idx < n; idx++) {
      auto x = qry(cur[idx].first, cur[idx].second);
      if (x.second - x.first < n - 1) {
        ans[idx] += (1 << i);
        cur[idx] = x;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout << ans[i] + 1 << ' ';
  }
  return 0;
}
