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 n;
int r[101010];
int spx[20][(1 << 20)];
int spn[20][(1 << 20)];
int gtx(int a, int b, int i) {
  a += (1 << 20) / 2;
  b += (1 << 20) / 2;
  a = max(a, (1 << 20) / 2);
  b = min(b, (1 << 20) - 1);
  int rv = spx[i][a];
  while (a < b) {
    if (a & 1) rv = max(rv, spx[i][a++]);
    if (~b & 1) rv = max(rv, spx[i][b--]);
    a /= 2;
    b /= 2;
  }
  if (a == b) rv = max(rv, spx[i][a]);
  return rv;
}
int gtn(int a, int b, int i) {
  a += (1 << 20) / 2;
  b += (1 << 20) / 2;
  a = max(a, (1 << 20) / 2);
  b = min(b, (1 << 20) - 1);
  int rv = spn[i][a];
  while (a < b) {
    if (a & 1) rv = min(rv, spn[i][a++]);
    if (~b & 1) rv = min(rv, spn[i][b--]);
    a /= 2;
    b /= 2;
  }
  if (a == b) rv = min(rv, spn[i][a]);
  return rv;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> r[i];
    spx[0][i + (1 << 20) / 2] = (i + r[i]);
    spn[0][i + (1 << 20) / 2] = (i - r[i]);
    spx[0][i + n + (1 << 20) / 2] = (i + n + r[i]);
    spn[0][i + n + (1 << 20) / 2] = (i + n - r[i]);
    spx[0][i + n + n + (1 << 20) / 2] = (i + n + n + r[i]);
    spn[0][i + n + n + (1 << 20) / 2] = (i + n + n - r[i]);
  }
  for (int i = (1 << 20) / 2 - 1; i; --i) {
    spx[0][i] = max(spx[0][2 * i], spx[0][2 * i + 1]);
    spn[0][i] = min(spn[0][2 * i], spn[0][2 * i + 1]);
  }
  for (int j = 1; j < 20; ++j) {
    for (int i = (1 << 20) / 2; i < (1 << 20); ++i) {
      spx[j][i] = gtx(spn[j - 1][i], spx[j - 1][i], j - 1);
      spn[j][i] = gtn(spn[j - 1][i], spx[j - 1][i], j - 1);
    }
    for (int i = (1 << 20) / 2 - 1; i; --i) {
      spx[j][i] = max(spx[j][2 * i], spx[j][2 * i + 1]);
      spn[j][i] = min(spn[j][2 * i], spn[j][2 * i + 1]);
    }
  }
  for (int ii = 0; ii < n; ++ii) {
    int ans = 0;
    int a = ii + n;
    int b = ii + n;
    for (int j = 19; j >= 0; --j) {
      int aa = gtn(a, b, j);
      int bb = gtx(a, b, j);
      if (bb - aa < n - 1) {
        a = aa;
        b = bb;
        ans += (1 << j);
      }
    }
    if (b - a < n - 1) ++ans;
    cout << ans << " ";
  }
  cout << "\n";
}
