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;
template <class T>
inline void chkmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void chkmin(T &a, T b) {
  if (a > b) a = b;
}
inline int read() {
  int sum = 0, p = 1;
  char ch = getchar();
  while (!(('0' <= ch && ch <= '9') || ch == '-')) ch = getchar();
  if (ch == '-') p = -1, ch = getchar();
  while ('0' <= ch && ch <= '9') sum = sum * 10 + ch - 48, ch = getchar();
  return sum * p;
}
const int maxn = 3e5 + 20;
const int maxp = 19;
int n, r[maxn];
int L[20][maxn], R[20][maxn];
int stmn[20][maxn], stmx[20][maxn];
int lg[maxn];
inline void init() {
  n = read();
  for (int i = (1), _end_ = (n); i <= _end_; i++)
    r[i] = read(), r[i + n] = r[i + n + n] = r[i];
  for (int i = (1), _end_ = (3 * n); i <= _end_; i++)
    L[0][i] = max(i - r[i], 1), R[0][i] = min(i + r[i], 3 * n);
  for (int i = (2), _end_ = (3 * n); i <= _end_; i++) lg[i] = lg[i >> 1] + 1;
}
inline int querymx(int l, int r) {
  int k = lg[r - l + 1];
  return max(stmx[k][l], stmx[k][r - (1 << k) + 1]);
}
inline int querymn(int l, int r) {
  int k = lg[r - l + 1];
  return min(stmn[k][l], stmn[k][r - (1 << k) + 1]);
}
int le[maxn], ri[maxn], ans[maxn];
inline void doing() {
  for (int j = (1), _end_ = (18); j <= _end_; j++) {
    for (int i = (1), _end_ = (3 * n); i <= _end_; i++)
      stmn[0][i] = L[j - 1][i], stmx[0][i] = R[j - 1][i];
    for (int jj = (1), _end_ = (18); jj <= _end_; jj++)
      for (int i = (1), _end_ = (3 * n - (1 << jj) + 1); i <= _end_; i++)
        stmn[jj][i] = min(stmn[jj - 1][i], stmn[jj - 1][i + (1 << jj - 1)]);
    for (int jj = (1), _end_ = (18); jj <= _end_; jj++)
      for (int i = (1), _end_ = (3 * n - (1 << jj) + 1); i <= _end_; i++)
        stmx[jj][i] = max(stmx[jj - 1][i], stmx[jj - 1][i + (1 << jj - 1)]);
    for (int i = (1), _end_ = (3 * n); i <= _end_; i++)
      L[j][i] = max(querymn(L[j - 1][i], R[j - 1][i]), 1);
    for (int i = (1), _end_ = (3 * n); i <= _end_; i++)
      R[j][i] = min(querymx(L[j - 1][i], R[j - 1][i]), 3 * n);
  }
  for (int i = (1), _end_ = (n); i <= _end_; i++) le[i] = ri[i] = i + n;
  for (int j = (18), _end_ = (0); j >= _end_; j--) {
    for (int i = (1), _end_ = (3 * n); i <= _end_; i++)
      stmn[0][i] = L[j][i], stmx[0][i] = R[j][i];
    for (int jj = (1), _end_ = (18); jj <= _end_; jj++)
      for (int i = (1), _end_ = (3 * n - (1 << jj) + 1); i <= _end_; i++)
        stmn[jj][i] = min(stmn[jj - 1][i], stmn[jj - 1][i + (1 << jj - 1)]);
    for (int jj = (1), _end_ = (18); jj <= _end_; jj++)
      for (int i = (1), _end_ = (3 * n - (1 << jj) + 1); i <= _end_; i++)
        stmx[jj][i] = max(stmx[jj - 1][i], stmx[jj - 1][i + (1 << jj - 1)]);
    for (int i = (1), _end_ = (n); i <= _end_; i++) {
      int LL = querymn(le[i], ri[i]), RR = querymx(le[i], ri[i]);
      if (RR - LL < n - 1) le[i] = LL, ri[i] = RR, ans[i] += 1 << j;
    }
  }
  for (int i = (1), _end_ = (n); i <= _end_; i++)
    if (le[i] - ri[i] < n - 1) ans[i]++;
  for (int i = (1), _end_ = (n); i <= _end_; i++) printf("%d ", ans[i]);
}
int main() {
  init();
  doing();
  return 0;
}
