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 long long mod = 998244353;
const long long MAGIC = 1 << 15;
int N;
const int INF = 1000 * 1000 * 1000;
const int MAXN = 1 << 20;
const int LG = 17;
int l[LG][MAXN >> 1];
int r[LG][MAXN >> 1];
int TL[LG][MAXN];
int TR[LG][MAXN];
int a[MAXN];
int n;
void build(int idx, int v, int tl, int tr) {
  if (tl == tr) {
    TL[idx][v] = l[idx][tl];
    TR[idx][v] = r[idx][tl];
    return;
  }
  int tm = (tl + tr) / 2;
  build(idx, v * 2, tl, tm);
  build(idx, v * 2 + 1, tm + 1, tr);
  TL[idx][v] = min(TL[idx][v * 2], TL[idx][v * 2 + 1]);
  TR[idx][v] = max(TR[idx][v * 2], TR[idx][v * 2 + 1]);
}
int getMin(int idx, int v, int tl, int tr, int l, int r) {
  if (l > r) return INF;
  if (tl == l && tr == r) {
    return TL[idx][v];
  }
  int tm = (tl + tr) / 2;
  return min(getMin(idx, v * 2, tl, tm, l, min(r, tm)),
             getMin(idx, v * 2 + 1, tm + 1, tr, max(tm + 1, l), r));
}
int getMax(int idx, int v, int tl, int tr, int l, int r) {
  if (l > r) return -INF;
  if (tl == l && tr == r) {
    return TR[idx][v];
  }
  int tm = (tl + tr) / 2;
  return max(getMax(idx, v * 2, tl, tm, l, min(r, tm)),
             getMax(idx, v * 2 + 1, tm + 1, tr, max(tm + 1, l), r));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  if (n == 1) {
    cout << 0;
    return 0;
  }
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i + 2 * n] = a[i + n] = a[i];
  }
  for (int i = 0; i < 3 * n; i++) {
    l[0][i] = i - a[i];
    r[0][i] = i + a[i];
  }
  for (int i = 1; i < LG; i++) {
    build(i - 1, 1, 0, 3 * n - 1);
    for (int j = n; j < 2 * n; j++) {
      l[i][j] = getMin(i - 1, 1, 0, 3 * n - 1, max(0, l[i - 1][j]),
                       min(3 * n - 1, r[i - 1][j]));
      r[i][j] = getMax(i - 1, 1, 0, 3 * n - 1, max(0, l[i - 1][j]),
                       min(3 * n - 1, r[i - 1][j]));
    }
    for (int j = 0; j < n; j++) {
      l[i][j] = l[i][j + n] - n;
      r[i][j] = r[i][j + n] - n;
      l[i][j + 2 * n] = l[i][j + n] + n;
      r[i][j + 2 * n] = r[i][j + n] + n;
    }
  }
  build(LG - 1, 1, 0, 3 * n - 1);
  for (int i = n; i < 2 * n; i++) {
    int curL = i, curR = i;
    int ans = 0;
    for (int j = LG - 1; j >= 0; j--) {
      int newL = getMin(j, 1, 0, 3 * n - 1, curL, curR),
          newR = getMax(j, 1, 0, 3 * n - 1, curL, curR);
      if (newR - newL + 1 < n) {
        ans += (1 << j);
        curL = newL;
        curR = newR;
      }
    }
    cout << ans + 1 << " ";
  }
}
