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 = 300050;
struct Segtree {
  int minn[N << 2], maxx[N << 2];
  void build(int *a, int *b, int l, int r, int pos) {
    if (l == r) {
      maxx[pos] = a[l];
      minn[pos] = b[l];
      return;
    }
    int mid = (l + r) >> 1, lson = pos << 1, rson = pos << 1 | 1;
    build(a, b, l, mid, lson), build(a, b, mid + 1, r, rson);
    maxx[pos] = max(maxx[lson], maxx[rson]);
    minn[pos] = min(minn[lson], minn[rson]);
  }
  int query_max(int l, int r, int pos, int L, int R) {
    if (l >= L && r <= R) return maxx[pos];
    int mid = (l + r) >> 1, lson = pos << 1, rson = pos << 1 | 1;
    if (mid < L)
      return query_max(mid + 1, r, rson, L, R);
    else if (mid >= R)
      return query_max(l, mid, lson, L, R);
    else
      return max(query_max(l, mid, lson, L, R),
                 query_max(mid + 1, r, rson, L, R));
  }
  int query_min(int l, int r, int pos, int L, int R) {
    if (l >= L && r <= R) return minn[pos];
    int mid = (l + r) >> 1, lson = pos << 1, rson = pos << 1 | 1;
    if (mid < L)
      return query_min(mid + 1, r, rson, L, R);
    else if (mid >= R)
      return query_min(l, mid, lson, L, R);
    else
      return min(query_min(l, mid, lson, L, R),
                 query_min(mid + 1, r, rson, L, R));
  }
} tr[22];
int n, a[N], f[22][N], g[22][N];
int solve(int x) {
  int l, r, t, ans = 0;
  for (int i = 0; i <= 20; i++) {
    if (f[i][x + n] - g[i][x + n] >= n - 1) {
      if (i) {
        l = g[i - 1][x + n], r = f[i - 1][x + n], t = i - 1,
        ans += 1 << (i - 1);
        break;
      } else
        return 1;
    }
  }
  for (int i = t - 1; ~i; i--) {
    int tmpr = tr[i].query_max(1, 3 * n, 1, l, r);
    int tmpl = tr[i].query_min(1, 3 * n, 1, l, r);
    if (tmpr - tmpl >= n - 1)
      ;
    else
      l = tmpl, r = tmpr, ans += 1 << i;
  }
  return ans + 1;
}
int main() {
  scanf("%d", &n);
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    a[n + i] = a[i], a[2 * n + i] = a[i];
  }
  for (int i = 1; i <= 3 * n; i++) {
    f[0][i] = min(i + a[i], 3 * n);
    g[0][i] = max(i - a[i], 1);
  }
  tr[0].build(f[0], g[0], 1, 3 * n, 1);
  for (int i = 1; i <= 21; i++) {
    for (int j = 1; j <= 3 * n; j++) {
      f[i][j] = tr[i - 1].query_max(1, 3 * n, 1, g[i - 1][j], f[i - 1][j]);
      g[i][j] = tr[i - 1].query_min(1, 3 * n, 1, g[i - 1][j], f[i - 1][j]);
    }
    tr[i].build(f[i], g[i], 1, 3 * n, 1);
  }
  for (int i = 1; i <= n; i++) printf("%d ", solve(i));
}
