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>
char ch;
bool fs;
void re(int& x) {
  while (ch = getchar(), ch < 33)
    ;
  if (ch == '-')
    fs = 1, x = 0;
  else
    fs = 0, x = ch - 48;
  while (ch = getchar(), ch > 33) x = x * 10 + ch - 48;
  if (fs) x = -x;
}
using namespace std;
int ll[300001], rr[300001], t[300001];
int n, m, e[300001], r[300001], ml[300001][19], mr[300001][19];
int lp[1 << 20], rp[1 << 20];
struct seg {
  int id, mn[1 << 20], mx[1 << 20];
  void build(int k, int a, int b) {
    lp[k] = a;
    rp[k] = b;
    if (a == b) {
      mn[k] = ml[a][id];
      mx[k] = mr[a][id];
      return;
    }
    build(k << 1, a, a + b >> 1);
    build(k << 1 | 1, (a + b >> 1) + 1, b);
    mn[k] = min(mn[k << 1], mn[k << 1 | 1]);
    mx[k] = max(mx[k << 1], mx[k << 1 | 1]);
  }
  int qmn(int k, int a, int b) {
    if (a <= lp[k] && b >= rp[k]) return mn[k];
    int m = lp[k] + rp[k] >> 1;
    if (b <= m)
      return qmn(k << 1, a, b);
    else if (a > m)
      return qmn(k << 1 | 1, a, b);
    else
      return min(qmn(k << 1, a, b), qmn(k << 1 | 1, a, b));
  }
  int qmx(int k, int a, int b) {
    if (a <= lp[k] && b >= rp[k]) return mx[k];
    int m = lp[k] + rp[k] >> 1;
    if (b <= m)
      return qmx(k << 1, a, b);
    else if (a > m)
      return qmx(k << 1 | 1, a, b);
    else
      return max(qmx(k << 1, a, b), qmx(k << 1 | 1, a, b));
  }
} tr[19];
int main() {
  re(n);
  for (int i = 1; i <= n; ++i) re(r[i]);
  m = n * 3;
  for (int i = 2; i <= m; ++i) e[i] = e[i >> 1] + 1;
  for (int i = n + 1; i <= m; ++i) {
    r[i] = r[i - n];
  }
  for (int i = 1; i <= m; ++i) {
    ll[i] = i;
    rr[i] = i;
    ml[i][0] = max(1, i - r[i]);
    mr[i][0] = min(m, i + r[i]);
  }
  tr[0].build(1, 1, m);
  for (int i = 1; i <= 18; ++i) {
    for (int j = 1; j <= m; ++j)
      ml[j][i] = tr[i - 1].qmn(1, ml[j][i - 1], mr[j][i - 1]),
      mr[j][i] = tr[i - 1].qmx(1, ml[j][i - 1], mr[j][i - 1]);
    tr[i].id = i, tr[i].build(1, 1, m);
  }
  for (int i = n + 1; i <= n + n; ++i) {
    for (int j = 18; j >= 0; --j) {
      int a = tr[j].qmn(1, ll[i], rr[i]), b = tr[j].qmx(1, ll[i], rr[i]);
      if (b - a + 1 < n) ll[i] = a, rr[i] = b, t[i] += 1 << j;
    }
    printf("%d ", t[i] + (rr[i] - ll[i] + 1 < n));
  }
}
