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 = (int)3e5 + 123, inf = 1e9, LOG = 20;
const long long INF = 1e18;
int n, m, a[N], l[LOG][N], r[LOG][N], mn[LOG][N], mx[LOG][N], lg[N], res[N];
pair<int, int> cur[N];
inline int getmn(int l, int r) {
  return min(mn[lg[r - l + 1]][l],
             mn[lg[r - l + 1]][r - (1 << lg[r - l + 1]) + 1]);
}
inline int getmx(int l, int r) {
  return max(mx[lg[r - l + 1]][l],
             mx[lg[r - l + 1]][r - (1 << lg[r - l + 1]) + 1]);
}
int main() {
  for (int i = 2; i < N; i++) lg[i] = lg[i / 2] + 1;
  scanf("%d", &n);
  if (n == 1) {
    printf("0");
    return 0;
  }
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    a[i] = x;
    a[i + n] = x;
    a[i + n + n] = x;
  }
  m = n + n + n;
  for (int i = 0; i < LOG; i++) {
    if (i == 0) {
      for (int j = 0; j < m; j++) {
        l[i][j] = max(0, j - a[j]);
        r[i][j] = min(m - 1, j + a[j]);
      }
    } else {
      for (int j = 0; j < m; j++) {
        l[i][j] = getmn(l[i - 1][j], r[i - 1][j]);
        r[i][j] = getmx(l[i - 1][j], r[i - 1][j]);
      }
    }
    for (int q = 0; q < LOG; q++)
      for (int j = 0; j < m; j++)
        if (q == 0) {
          mn[q][j] = l[i][j];
          mx[q][j] = r[i][j];
        } else if (j + (1 << (q - 1)) < m) {
          mn[q][j] = min(mn[q - 1][j], mn[q - 1][j + (1 << (q - 1))]);
          mx[q][j] = max(mx[q - 1][j], mx[q - 1][j + (1 << (q - 1))]);
        }
  }
  for (int i = n; i < n + n; i++) cur[i] = {i, i};
  for (int i = LOG - 1; i >= 0; i--) {
    for (int q = 0; q < LOG; q++)
      for (int j = 0; j < m; j++)
        if (q == 0) {
          mn[q][j] = l[i][j];
          mx[q][j] = r[i][j];
        } else if (j + (1 << (q - 1)) < m) {
          mn[q][j] = min(mn[q - 1][j], mn[q - 1][j + (1 << (q - 1))]);
          mx[q][j] = max(mx[q - 1][j], mx[q - 1][j + (1 << (q - 1))]);
        }
    for (int j = n; j < n + n; j++) {
      pair<int, int> nxt;
      nxt.first = getmn(cur[j].first, cur[j].second);
      nxt.second = getmx(cur[j].first, cur[j].second);
      if (nxt.second - nxt.first + 1 < n) {
        cur[j] = nxt;
        res[j] += (1 << i);
      }
    }
  }
  for (int i = n; i < n + n; i++) printf("%d ", res[i] + 1);
  return 0;
}
