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 = 3e5 + 11;
const long long oo = 1e17 + 11;
int tcases = 1;
int N, M;
int A[maxN];
pair<int, int> range[maxN][19];
int calf = 0, calg = 0, initT = 0;
struct {
  pair<int, int> seg[maxN * 4];
  int ii;
  pair<int, int> cmp(pair<int, int> X, pair<int, int> Y) {
    return make_pair(min(X.first, Y.first), max(X.second, Y.second));
  }
  void build(int k, int l, int r) {
    if (l == r) {
      seg[k] = range[l][ii];
      return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    seg[k] = cmp(seg[k << 1], seg[k << 1 | 1]);
  }
  void init(int i) {
    ii = i;
    build(1, 1, 3 * N);
  }
  pair<int, int> find(int k, int l, int r, int L, int R) {
    if (l > R || L > r) return range[L][ii];
    if (L <= l && r <= R) return seg[k];
    int mid = (l + r) >> 1;
    return cmp(find(k << 1, l, mid, L, R), find(k << 1 | 1, mid + 1, r, L, R));
  }
} it;
void build() {
  for (int i = 1; i <= 3 * N; ++i) {
    range[i][0] = make_pair(max(i - A[i], 1), min(i + A[i], 3 * N));
  }
  it.init(0);
  for (int j = 1; j <= 18; ++j) {
    for (int i = 1; i <= 3 * N; ++i) {
      range[i][j] =
          it.find(1, 1, 3 * N, range[i][j - 1].first, range[i][j - 1].second);
    }
    it.init(j);
  }
}
int res[maxN];
pair<int, int> pos[maxN];
void testcase() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
  if (N <= 1) {
    putchar('0');
    return;
  }
  for (int i = 1; i <= N; ++i) {
    A[i + N] = A[i + 2 * N] = A[i];
  }
  build();
  for (int i = 1; i <= N; ++i) pos[i] = make_pair(i + N, i + N);
  for (int j = 18; j >= 0; --j) {
    it.init(j);
    for (int i = 1; i <= N; ++i) {
      pair<int, int> tmp = it.find(1, 1, 3 * N, pos[i].first, pos[i].second);
      if (tmp.second - tmp.first + 1 < N) {
        pos[i] = tmp;
        res[i] |= (1 << j);
      }
    }
  }
  for (int i = 1; i <= N; ++i) {
    printf("%d ", res[i] + 1);
  }
}
int main() {
  for (int i = 1; i <= tcases; ++i) testcase();
  return 0;
}
