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 = 303030;
int n;
int a[N], lg[N], Min[20][N], Max[20][N], val[2][N], L[20][N], R[20][N];
void build(int a[][N], int n, int o, int val[]) {
  for (int i = (0); i < (n); ++i) a[0][i] = i;
  for (int i = (1); i < (lg[n] + 1); ++i)
    for (int j = (0); j < (n - (1 << i) + 1); ++j) {
      int x = a[i - 1][j], y = a[i - 1][j + (1 << i >> 1)];
      a[i][j] = ((val[x] < val[y]) ^ o) ? x : y;
    }
}
int qry(int a[][N], int l, int r, int o, int val[]) {
  if (l > r) swap(l, r);
  int i = lg[r - l + 1];
  int x = a[i][l], y = a[i][r + 1 - (1 << i)];
  return ((val[x] < val[y]) ^ o) ? x : y;
}
int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  cin >> n;
  for (int i = (0); i < (n); ++i) cin >> a[i];
  if (n == 1) {
    cout << 0 << "\n";
    return 0;
  }
  for (int i = (n); i < (n * 3); ++i) a[i] = a[i - n];
  for (int i = (2); i < (n * 3 + 1); ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = (0); i < (n * 3); ++i) L[0][i] = val[0][i] = max(i - a[i], 0);
  build(Min, n * 3, 0, val[0]);
  for (int i = (0); i < (n * 3); ++i)
    R[0][i] = val[1][i] = min(i + a[i], 3 * n - 1);
  build(Max, n * 3, 1, val[1]);
  for (int i = (1); i < (20); ++i) {
    for (int j = (0); j < (n * 3); ++j) {
      int l = qry(Min, L[i - 1][j], R[i - 1][j], 0, val[0]);
      int r = qry(Max, L[i - 1][j], R[i - 1][j], 1, val[1]);
      L[i][j] = min(L[i - 1][l], L[i - 1][r]);
      R[i][j] = max(R[i - 1][l], R[i - 1][r]);
    }
  }
  for (int t = (0); t < (n); ++t) {
    int j = t + n, l = j, r = j, ans = 0;
    for (int i = (20) - 1; i >= (0); --i) {
      int x = qry(Min, l, r, 0, val[0]);
      int y = qry(Max, l, r, 1, val[1]);
      int tl = min(L[i][x], L[i][y]);
      int tr = max(R[i][x], R[i][y]);
      if (tr - tl + 1 < n) {
        ans += 1 << i;
        l = tl, r = tr;
      }
    }
    cout << ans + 1 << " \n"[t == n - 1];
  }
  return 0;
}
