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 maxN = 300001, maxTS = 1 << 20, INF = 1 << 20, maxL = 20;
inline void remin(int& a, int b) { a = min(a, b); }
inline void remax(int& a, int b) { a = max(a, b); }
struct Tree {
  int offset, qbegin, qend, resmn, resmx;
  int mn[maxTS], mx[maxTS];
  void querypriv(int v, int left, int right) {
    if (left >= qend or right <= qbegin) return;
    if (left >= qbegin and right <= qend) {
      remin(resmn, mn[v]);
      remax(resmx, mx[v]);
      return;
    }
    querypriv(v * 2, left, (left + right) / 2);
    querypriv(v * 2 + 1, (left + right) / 2, right);
  }
  void resize(int n) {
    for (offset = 1; offset < n; offset *= 2)
      ;
    for (int(i) = (1); (i) < (offset * 2); (i)++) mn[i] = INF, mx[i] = -INF;
  }
  void init(pair<int, int>* t, int n) {
    for (int(i) = (0); (i) < (n); (i)++)
      mn[offset + i] = t[i].first, mx[offset + i] = t[i].second;
    for (int i = offset - 1; i > 0; i--)
      mn[i] = min(mn[i * 2], mn[i * 2 + 1]),
      mx[i] = max(mx[i * 2], mx[i * 2 + 1]);
  }
  pair<int, int> query(int a, int b) {
    qbegin = a + offset;
    qend = b + offset + 1;
    resmn = INF;
    resmx = -INF;
    querypriv(1, offset, offset * 2);
    return {resmn, resmx};
  }
} tree[maxL];
pair<int, int> dp[maxL][maxN];
int n, r[maxN];
int moveleft(int a) { return max(a - n, 0); }
int moveright(int a) { return min(a + n, n * 3 - 1); }
int len(pair<int, int> a) { return a.second - a.first + 1; }
int main() {
  scanf("%d", &n);
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  for (int(i) = (n); (i) < (n * 2); (i)++)
    scanf("%d", r + i), remin(r[i], n / 2);
  for (int(i) = (n); (i) < (n * 2); (i)++) dp[0][i] = {i - r[i], i + r[i]};
  for (int(s) = (1); (s) < (maxL); (s)++) {
    for (int(i) = (n); (i) < (n * 2); (i)++) {
      dp[s - 1][i - n] = {moveleft(dp[s - 1][i].first),
                          moveleft(dp[s - 1][i].second)};
      dp[s - 1][i + n] = {moveright(dp[s - 1][i].first),
                          moveright(dp[s - 1][i].second)};
    }
    tree[s - 1].resize(n * 3);
    tree[s - 1].init(dp[s - 1], n * 3);
    for (int(i) = (n); (i) < (n * 2); (i)++)
      dp[s][i] = tree[s - 1].query(dp[s - 1][i].first, dp[s - 1][i].second);
  }
  for (int(i) = (n); (i) < (n * 2); (i)++) {
    int s = maxL - 2, res = 0;
    pair<int, int> ran = {i, i}, newran;
    while (true) {
      while (s >= 0 and len(newran = tree[s].query(ran.first, ran.second)) >= n)
        s--;
      if (s == -1) break;
      res |= 1 << s;
      ran = newran;
    }
    printf("%d ", res + 1);
  }
  printf("\n");
  return 0;
}
