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 N = 1e5;
int n, A[3 * N + 2], Leaf[3 * N + 2];
pair<int, int> P[3 * N + 2][19], Tree[4 * 3 * N + 2][17];
void input() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> A[i];
  for (int i = n + 1; i <= 3 * n; ++i) A[i] = A[i - n];
}
pair<int, int> min(const pair<int, int> &a, const pair<int, int> &b) {
  return {min(a.first, b.first), max(a.second, b.second)};
}
void update(int j, int u, pair<int, int> val) {
  int id = Leaf[u];
  Tree[id][j] = val;
  id >>= 1;
  while (id) {
    Tree[id][j] = min(Tree[(id << 1)][j], Tree[(id << 1 | 1)][j]);
    id >>= 1;
  }
}
pair<int, int> nex;
void get(int j, int id, int first, int second, int u, int v) {
  if (first >= u && second <= v) {
    nex = min(nex, Tree[id][j]);
    return;
  }
  if (v <= ((first + second) / 2))
    get(j, (id << 1), first, ((first + second) / 2), u, v);
  else if (u > ((first + second) / 2))
    get(j, (id << 1 | 1), ((first + second) / 2) + 1, second, u, v);
  else {
    get(j, (id << 1), first, ((first + second) / 2), u, v);
    get(j, (id << 1 | 1), ((first + second) / 2) + 1, second, u, v);
  }
}
void dfs(int id, int first, int second) {
  if (first == second) {
    Leaf[first] = id;
    return;
  }
  dfs((id << 1), first, ((first + second) / 2));
  dfs((id << 1 | 1), ((first + second) / 2) + 1, second);
}
void init() {
  dfs(1, 1, 3 * n);
  for (int i = 1; i <= 3 * n; ++i)
    P[i][0] = {max(i - A[i], 1), min(i + A[i], 3 * n)};
  for (int j = 1; j <= 17; ++j) {
    for (int i = 1; i <= 3 * n; ++i) update(j - 1, i, P[i][j - 1]);
    if (j == 17) break;
    for (int i = 1; i <= 3 * n; ++i) {
      nex = {i, i};
      get(j - 1, 1, 1, 3 * n, max(P[i][j - 1].first, 1),
          min(P[i][j - 1].second, 3 * n));
      P[i][j] = nex;
    }
  }
}
void solve() {
  init();
  for (int i = n + 1; i <= n + n; ++i) {
    int ans = 0;
    pair<int, int> pos = {i, i};
    for (int j = 16; j >= 0; --j) {
      nex = pos;
      get(j, 1, 1, 3 * n, pos.first, pos.second);
      if (nex.second - nex.first + 1 <= n) pos = nex, ans += 1 << j;
    }
    cout << (pos.second - pos.first + 1 < n ? ans + 1 : ans) << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  input();
  solve();
  return 0;
}
