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>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
const int LGN = 18;
const int maxn = 1 << LGN;
const int INF = 1e9;
struct SegmentTree {
  int dpmax[2 * maxn], dpmin[2 * maxn];
  SegmentTree() {
    fill_n(dpmax, 2 * maxn, -INF);
    fill_n(dpmin, 2 * maxn, +INF);
  }
  void update(int i, int vmax, int vmin) {
    dpmax[i + maxn] = vmax;
    dpmin[i + maxn] = vmin;
  }
  void build_tree() {
    for (int i = maxn; --i > 0;) {
      dpmax[i] = max(dpmax[2 * i], dpmax[2 * i + 1]);
      dpmin[i] = min(dpmin[2 * i], dpmin[2 * i + 1]);
    }
  }
  int qmax(int a, int b) {
    int ra = -INF, rb = -INF;
    for (a += maxn, b += maxn; a < b; a /= 2, b /= 2) {
      if (a & 1) ra = max(ra, dpmax[a++]);
      if (b & 1) rb = max(rb, dpmax[--b]);
    }
    return max(ra, rb);
  }
  int qmin(int a, int b) {
    int ra = INF, rb = INF;
    for (a += maxn, b += maxn; a < b; a /= 2, b /= 2) {
      if (a & 1) ra = min(ra, dpmin[a++]);
      if (b & 1) rb = min(rb, dpmin[--b]);
    }
    return min(ra, rb);
  }
};
SegmentTree trees[LGN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n;
  cin >> n;
  vector<int> A(n + n);
  for (auto i = (0); i != (n); ++i) cin >> A[i];
  for (auto i = (0); i != (n); ++i) A[i + n] = A[i];
  int n2 = n + n;
  for (int i = 0; i < n2; i++) {
    trees[0].update(i, i + A[i], i - A[i]);
  }
  trees[0].build_tree();
  for (int i = 1; i < LGN; i++) {
    for (int j = 0; j < n2; j++) {
      int rhs = min(n2 - 1, trees[i - 1].dpmax[j + maxn]);
      int lhs = max(0, trees[i - 1].dpmin[j + maxn]);
      assert(lhs <= rhs);
      trees[i].update(j, trees[i - 1].qmax(lhs, rhs + 1),
                      trees[i - 1].qmin(lhs, rhs + 1));
    }
    trees[i].build_tree();
  }
  for (int i = 0; i < n; i++) {
    int i2 = i + n + 1;
    int il = i, ir = i2 - 1;
    int answer = 0;
    int lastMAX = LGN;
    while (lastMAX > 0) {
      assert(i <= il && il < ir && ir <= i + n);
      int kd = lastMAX - 1;
      int lhs, rhs;
      while (kd >= 0) {
        lhs = max(trees[kd].qmax(i, il + 1), trees[kd].qmax(ir, i2) - n);
        rhs = min(trees[kd].qmin(i, il + 1) + n, trees[kd].qmin(ir, i2));
        if (lhs < rhs - 1) break;
        kd--;
      }
      if (kd < 0) break;
      assert(~answer & (1 << kd));
      answer |= 1 << kd;
      lastMAX = kd;
      il = lhs;
      ir = rhs;
    }
    if (il + 1 < ir) answer++;
    printf("%d ", answer);
  }
  printf("\n");
  return 0;
}
