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;
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
long long rnxt[100010][20];
long long lnxt[100010][20];
int r[100010];
int b[100010 * 3];
int n;
int mx[3 * 100010][20];
int comp(int u, int v) {
  if (b[u] > b[v]) return u;
  return v;
}
int calc(int l, int r) {
  int k = 31 - __builtin_clz(r - l + 1);
  return comp(mx[l][k], mx[r - (1 << k) + 1][k]);
}
void pre(int n) {
  for (int i = 1; i <= n; i++) mx[i][0] = i;
  for (int j = 1; j < 20; j++) {
    for (int i = 1; i <= n; i++) {
      mx[i][j] = comp(mx[i][j - 1], mx[min(n, i + (1 << j - 1))][j - 1]);
    }
  }
}
int c(long long first) {
  first = (first % n + n) % n;
  if (first == 0) first = n;
  return first;
}
int main() {
  gn(n);
  for (int i = 1; i <= n; i++) gn(r[i]);
  if (n == 1) {
    cout << 0 << ' ';
    return 0;
  }
  for (int i = 1; i <= n * 3; i++) {
    int first = i % n;
    if (first == 0) first = n;
    b[i] = r[first] + i;
  }
  pre(3 * n);
  for (int i = n + 1; i <= 2 * n; i++) {
    int id = i % n;
    if (id == 0) id = n;
    int first = calc(i - r[id], i + r[id]);
    rnxt[id][0] = first - i;
  }
  for (int i = 1; i <= n * 3; i++) {
    int first = i % n;
    if (first == 0) first = n;
    b[i] = -(i - r[first]);
  }
  pre(3 * n);
  for (int i = n + 1; i <= n * 2; i++) {
    int id = i % n;
    if (id == 0) id = n;
    int first = calc(i - r[id], i + r[id]);
    lnxt[id][0] = i - first;
  }
  for (int j = 1; j < 20; j++)
    for (int i = 1; i <= n; i++) {
      long long u = lnxt[i][j - 1], v = rnxt[i][j - 1];
      int ux = c(rnxt[c(i - u)][j - 1] - u + i);
      int vx = c(rnxt[c(i + v)][j - 1] + v + i);
      if (rnxt[c(i - u)][j - 1] - u + r[ux] > rnxt[c(i + v)][j - 1] + v + r[vx])
        rnxt[i][j] = rnxt[c(i - u)][j - 1] - u;
      else
        rnxt[i][j] = rnxt[c(i + v)][j - 1] + v;
      ux = c(i - lnxt[c(i - u)][j - 1] - u);
      vx = c(i - lnxt[c(i + v)][j - 1] + v);
      if (lnxt[c(i - u)][j - 1] + u + r[ux] > lnxt[c(i + v)][j - 1] - v + r[vx])
        lnxt[i][j] = lnxt[c(i - u)][j - 1] + u;
      else
        lnxt[i][j] = lnxt[c(i + v)][j - 1] - v;
    }
  for (int i = 1; i <= n; i++) {
    if (r[i] * 2 >= n - 1) {
      printf("%d ", 1);
      continue;
    }
    int ans = 0;
    long long ls = 0, rs = 0;
    for (int j = 20 - 1; j >= 0; j--) {
      long long rs1 = rnxt[c(rs + i)][j] + rs;
      long long rs2 = rnxt[c(i - ls)][j] - ls;
      long long ls1 = lnxt[c(i - ls)][j] + ls;
      long long ls2 = lnxt[c(i + rs)][j] - rs;
      if (rs1 + r[c(i + rs1)] < rs2 + r[c(i + rs2)]) swap(rs1, rs2);
      if (ls1 + r[c(i - ls1)] < ls2 + r[c(i - ls2)]) swap(ls1, ls2);
      if (rs1 + r[c(i + rs1)] + ls1 + r[c(i - ls1)] < n - 1) {
        ans ^= (1 << j);
        rs = rs1;
        ls = ls1;
      }
    }
    printf("%d ", ans + 2);
  }
}
