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 mxN = 1e5;
int n, l[17][17][mxN], r[17][17][mxN];
pair<int, int> qry(int i, int l2, int r2) {
  int b = 31 - __builtin_clz(r2 - l2 + 1);
  return {max(l[i][b][l2],
              l[i][b][(r2 - (1 << b) + 1) % n] - (r2 - (1 << b) + 1 - l2)),
          max(r[i][b][(r2 - (1 << b) + 1) % n],
              r[i][b][l2] - (r2 - (1 << b) + 1 - l2))};
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  if (n == 1) {
    cout << 0;
    return 0;
  }
  for (int i = 0; i < n; ++i) cin >> l[0][0][i], r[0][0][i] = l[0][0][i];
  for (int i = 1; i < 17; ++i) {
    int a = 1 << (i - 1);
    for (int j = 0; j < n; ++j) {
      l[0][i][j] = max(l[0][i - 1][j], l[0][i - 1][(j + a) % n] - a);
      r[0][i][j] = max(r[0][i - 1][(j + a) % n], r[0][i - 1][j] - a);
    }
  }
  for (int i = 1; i < 17; ++i) {
    for (int j = 0; j < 17; ++j) {
      int a = 1 << j;
      for (int k = 0; k < n; ++k) {
        int l2 = k - l[i - 1][j][k], r2 = k + a - 1 + r[i - 1][j][k];
        if (r2 - l2 >= n - 1) {
          l[i][j][k] = r[i][j][k] = n;
          continue;
        }
        if (l2 < 0) {
          l2 += n;
          r2 += n;
        }
        tie(l[i][j][k], r[i][j][k]) = qry(i - 1, l2, r2);
        l[i][j][k] += l[i - 1][j][k];
        r[i][j][k] += r[i - 1][j][k];
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    int l2 = i, r2 = i, ans = 1, l3, r3;
    for (int j = 16; j >= 0; --j) {
      tie(l3, r3) = qry(j, l2, r2);
      l3 = l2 - l3;
      r3 += r2;
      if (r3 - l3 < n - 1) {
        ans += 1 << j;
        l2 = l3;
        r2 = r3;
        if (l2 < 0) {
          l2 += n;
          r2 += n;
        }
      }
    }
    cout << ans << " ";
  }
}
