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 pair<int, int> full(-1, -1);
int n;
pair<int, int> a[100010];
pair<int, int> f[17][100010 * 4];
pair<int, int> gg(pair<int, int> x, pair<int, int> y) {
  if (x == full) return x;
  if (y == full) return y;
  if (x.first <= x.second && y.first <= y.second) {
    pair<int, int> s(min(x.first, y.first), max(x.second, y.second));
    if (s.first == 0 && s.second == n - 1) return full;
    return s;
  }
  int le = 0, ri = n - 1;
  if (x.first > x.second) {
    le = max(le, x.second);
    ri = min(ri, x.first);
  }
  if (y.first > y.second) {
    le = max(le, y.second);
    ri = min(ri, y.first);
  }
  if (x.first <= x.second) {
    if (x.first <= le + 1) le = max(le, x.second);
    if (x.second >= ri - 1) ri = min(ri, x.first);
  }
  if (y.first <= y.second) {
    if (y.first <= le + 1) le = max(le, y.second);
    if (y.second >= ri - 1) ri = min(ri, y.first);
  }
  if (le >= ri - 1) return full;
  return make_pair(ri, le);
}
void blt(pair<int, int>* f, int p, int l, int r) {
  if (l == r - 1) {
    f[p] = a[l];
    return;
  }
  int mid = (l + r) / 2;
  blt(f, p * 2 + 1, l, mid);
  blt(f, p * 2 + 2, mid, r);
  f[p] = gg(f[p * 2 + 1], f[p * 2 + 2]);
}
pair<int, int> ask(pair<int, int>* f, int p, int l, int r, int L, int R) {
  if (L <= l && r <= R) return f[p];
  int mid = (l + r) / 2;
  if (R <= mid) return ask(f, p * 2 + 1, l, mid, L, R);
  if (L >= mid) return ask(f, p * 2 + 2, mid, r, L, R);
  return gg(ask(f, p * 2 + 1, l, mid, L, R), ask(f, p * 2 + 2, mid, r, L, R));
}
pair<int, int> ask(pair<int, int>* f, pair<int, int> s) {
  if (s == full) return s;
  if (s.first <= s.second) return ask(f, 0, 0, n, s.first, s.second + 1);
  return gg(ask(f, 0, 0, n, s.first, n), ask(f, 0, 0, n, 0, s.second + 1));
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x * 2 + 1 >= n)
      a[i] = full;
    else {
      int l = (i - x + n) % n;
      int r = (i + x) % n;
      a[i] = make_pair(l, r);
    }
  }
  if (n == 1) {
    puts("0");
    return 0;
  }
  blt(f[0], 0, 0, n);
  for (int l = 1; l <= 16; l++) {
    for (int i = 0; i < n; i++) a[i] = ask(f[l - 1], a[i]);
    blt(f[l], 0, 0, n);
  }
  for (int i = 0; i < n; i++) {
    int S = 0;
    pair<int, int> s = make_pair(i, i);
    for (int l = 16; l >= 0; l--) {
      pair<int, int> t = ask(f[l], s);
      if (t != full) {
        S += (1 << l);
        s = t;
      }
    }
    S++;
    cout << S << (i == n - 1 ? '\n' : ' ');
  }
  return 0;
}
