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 MAXN = 1 << 20;
pair<int, int> val[20][MAXN], tmp[MAXN];
int rr[MAXN], n;
pair<int, int> pushup(const pair<int, int> &a, const pair<int, int> &b) {
  return pair<int, int>(min(a.first, b.first), max(a.second, b.second));
}
void build(pair<int, int> *v, pair<int, int> *a, int l = 1, int r = n * 3,
           int k = 1) {
  if (l == r) {
    v[k] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(v, a, l, mid, k << 1);
  build(v, a, mid + 1, r, k << 1 | 1);
  v[k] = pushup(v[k << 1], v[k << 1 | 1]);
}
pair<int, int> ask(pair<int, int> *v, int a, int b, int l = 1, int r = n * 3,
                   int k = 1) {
  if (a > r || b < l) return pair<int, int>(n * 3, 0);
  if (a <= l && b >= r) return v[k];
  int mid = (l + r) >> 1;
  return pushup(ask(v, a, b, l, mid, k << 1),
                ask(v, a, b, mid + 1, r, k << 1 | 1));
}
int main() {
  scanf("%d", &n);
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", rr + i);
    tmp[i] = pair<int, int>(max(1, i - rr[i]), min(n * 3, i + rr[i]));
  }
  for (int i = n + 1; i <= n + n; i++)
    tmp[i] = pair<int, int>(max(1, i - rr[i - n]), min(n * 3, i + rr[i - n]));
  for (int i = n + n + 1; i <= n * 3; i++)
    tmp[i] = pair<int, int>(max(1, i - rr[i - n - n]),
                            min(n * 3, i + rr[i - n - n]));
  build(val[0], tmp);
  for (int i = 1; i < 20; i++) {
    for (int j = 1; j <= n * 3; j++)
      tmp[j] = ask(val[i - 1], tmp[j].first, tmp[j].second);
    build(val[i], tmp);
  }
  for (int i = 1; i <= n; i++) {
    int nl = i + n, nr = i + n, res = 0;
    for (int j = 19; ~j; j--) {
      pair<int, int> p = ask(val[j], nl, nr);
      if (p.second - p.first + 1 >= n) continue;
      nl = p.first, nr = p.second, res += 1 << j;
    }
    printf("%d ", res + 1);
  }
  return 0;
}
