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>
int B = 16;
int L[17][100005], R[17][100005], a[100005], n, lg[100005];
struct spraseTable {
  int T[100005][17];
  void init(int *a, int flag) {
    for (int i = n; i >= 1; --i) {
      T[i][0] = a[i] + i * flag;
      for (int j = 1; i + (1 << j) <= n + 1; ++j)
        T[i][j] = std::max(T[i][j - 1], T[i + (1 << (j - 1))][j - 1]);
    }
  }
  int query(int l, int r) {
    int L = lg[r - l + 1];
    return std::max(T[l][L], T[r - (1 << L) + 1][L]);
  }
  int query_left(int i, int dis) {
    if (i - dis >= 1)
      return i + query(i - dis, i);
    else {
      int ans1 = i + query(1, i);
      int rd = dis - (i - 1);
      int ans2 = i + n + query(n - rd + 1, n);
      return std::max(ans1, ans2);
    }
  }
  int query_left2(int i, int dis) {
    if (i + dis <= n)
      return i + query(i, i + dis);
    else {
      int ans1 = query(i, n) + i;
      int ld = i + dis - n;
      int ans2 = query(1, ld) + i - n;
      return std::max(ans1, ans2);
    }
  }
  int query_right(int i, int dis) {
    if (i + dis <= n)
      return query(i, i + dis) - i;
    else {
      int ans1 = query(i, n) - i;
      int ld = i + dis - n;
      int ans2 = query(1, ld) - i + n;
      return std::max(ans1, ans2);
    }
  }
  int query_right2(int i, int dis) {
    if (i - dis >= 1)
      return -i + query(i - dis, i);
    else {
      int ans1 = -i + query(1, i);
      int rd = dis - (i - 1);
      int ans2 = -i - n + query(n - rd + 1, n);
      return std::max(ans1, ans2);
    }
  }
} LT[17], RT[17];
int main() {
  scanf("%d", &n);
  if (n == 1) {
    puts("0");
    return 0;
  }
  lg[0] = -1;
  for (int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) R[0][i] = L[0][i] = std::min(n - 1, a[i]);
  for (int i = 1; i <= B; ++i) {
    RT[i - 1].init(R[i - 1], 1);
    for (int j = 1; j <= n; ++j) {
      if (R[i - 1][j] == n - 1)
        R[i][j] = n - 1;
      else
        R[i][j] =
            std::min(n - 1, std::max(RT[i - 1].query_right(j, R[i - 1][j]),
                                     RT[i - 1].query_right2(j, L[i - 1][j])));
    }
    LT[i - 1].init(L[i - 1], -1);
    for (int j = 1; j <= n; ++j) {
      if (L[i - 1][j] == n - 1)
        L[i][j] = n - 1;
      else
        L[i][j] =
            std::min(n - 1, std::max(LT[i - 1].query_left(j, L[i - 1][j]),
                                     LT[i - 1].query_left2(j, R[i - 1][j])));
    }
  }
  RT[B].init(R[B], 1);
  LT[B].init(L[B], -1);
  for (int i = 1; i <= n; ++i) {
    int ans = 0, ld = 0, rd = 0;
    for (int j = B; j >= 0; j--) {
      int a = std::max(RT[j].query_right(i, rd), RT[j].query_right2(i, ld)),
          b = std::max(LT[j].query_left(i, ld), LT[j].query_left2(i, rd));
      if (a + b < n - 1) {
        ans += (1 << j);
        rd = a;
        ld = b;
      }
    }
    printf("%d ", ans + 1);
  }
  return 0;
}
