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;
int read() {
  int tot = 0, fh = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') fh = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    tot = tot * 10 + c - '0';
    c = getchar();
  }
  return tot * fh;
}
const int maxn = 2e5 + 100;
int f[22][maxn], g[22][maxn], n, a[maxn], l[maxn][22], r[maxn][22], ans[maxn],
    posL[maxn], posR[maxn], LOG[maxn];
void buildL(int tag) {
  for (int i = 1; i <= n; i++) f[0][i] = l[i][tag] - i;
  for (int i = 1; i <= 20; i++)
    for (int j = 1; j <= n; j++)
      f[i][j] = max(f[i - 1][j], f[i - 1][min(n, j + (1 << (i - 1)))]);
}
void buildR(int tag) {
  for (int i = 1; i <= n; i++) g[0][i] = r[i][tag] + i;
  for (int i = 1; i <= 20; i++)
    for (int j = 1; j <= n; j++)
      g[i][j] = max(g[i - 1][j], g[i - 1][min(n, j + (1 << (i - 1)))]);
}
int queryL(int l, int r) {
  if (l > r) swap(l, r);
  int len = r - l + 1;
  return max(f[LOG[len]][l], f[LOG[len]][r - (1 << LOG[len]) + 1]);
}
int queryR(int l, int r) {
  if (l > r) swap(l, r);
  int len = r - l + 1;
  return max(g[LOG[len]][l], g[LOG[len]][r - (1 << LOG[len]) + 1]);
}
int chk(int x) {
  if (x <= 0) return x + n;
  if (x > n) return x - n;
  return x;
}
int main() {
  n = read();
  LOG[1] = 0;
  for (int i = 2; i <= n; i++) LOG[i] = LOG[i >> 1] + 1;
  if (n == 1) {
    cout << 0 << "\n";
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    a[i] = min(a[i], n - 1);
  }
  for (int i = 1; i <= n; i++) l[i][0] = r[i][0] = a[i];
  for (int i = 1; i <= 20; i++) {
    buildL(i - 1);
    buildR(i - 1);
    for (int j = 1; j <= n; j++) {
      if (l[j][i - 1] == n - 1) {
        l[j][i] = n - 1;
        continue;
      }
      int pos = j - l[j][i - 1];
      if (max(1, pos) <= j) l[j][i] = j + queryL(max(1, pos), j);
      if (pos < 1) l[j][i] = max(l[j][i], j + n + queryL(pos + n, n));
      pos = j + r[j][i - 1];
      if (min(pos, n) >= j) l[j][i] = max(l[j][i], j + queryL(j, min(pos, n)));
      if (pos > n) l[j][i] = max(l[j][i], j - n + queryL(1, pos - n));
      l[j][i] = min(l[j][i], n - 1);
    }
    for (int j = 1; j <= n; j++) {
      if (r[j][i - 1] == n - 1) {
        r[j][i] = n - 1;
        continue;
      }
      int pos = j + r[j][i - 1];
      if (j + 1 <= min(pos, n)) r[j][i] = -j + queryR(j + 1, min(pos, n));
      if (pos > n) r[j][i] = max(r[j][i], -j + n + queryR(1, pos - n));
      pos = j - l[j][i - 1];
      if (max(1, pos) <= j - 1)
        r[j][i] = max(r[j][i], -j + queryR(max(1, pos), j - 1));
      if (pos < 1) r[j][i] = max(r[j][i], -j - n + queryR(pos + n, n));
      r[j][i] = min(r[j][i], n - 1);
    }
  }
  for (int i = 1; i <= n; i++) posL[i] = posR[i] = i;
  for (int i = 20; i >= 0; i--) {
    buildL(i);
    buildR(i);
    for (int j = 1; j <= n; j++) {
      int numL = 0, numR = 0;
      if (posL[j] <= j)
        numL = j + queryL(posL[j], j);
      else
        numL = max(j + queryL(1, j), j + n + queryL(posL[j], n));
      if (posR[j] >= j)
        numL = max(numL, j + queryL(j, posR[j]));
      else
        numL = max(numL, max(j + queryL(j, n), j - n + queryL(1, posR[j])));
      if (posR[j] >= j)
        numR = -j + queryR(j, posR[j]);
      else
        numR = max(-j + queryR(j, n), -j + n + queryR(1, posR[j]));
      if (posL[j] <= j)
        numR = max(numR, -j + queryR(posL[j], j));
      else
        numR = max(numR, max(-j + queryR(1, j), -j - n + queryR(posL[j], n)));
      if (numL + numR < n - 1) {
        ans[j] += (1 << i);
        posL[j] = chk(j - numL);
        posR[j] = chk(j + numR);
      }
    }
  }
  for (int i = 1; i <= n; i++) cout << ans[i] + 1 << " ";
  cout << "\n";
  return 0;
}
