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 inf = 1e9 + 7;
const long long INF = 1e18L + 7;
template <class n, class second>
ostream &operator<<(ostream &p, pair<n, second> x) {
  return p << "<" << x.first << ", " << x.second << ">";
}
template <class n>
auto operator<<(ostream &p, n y) ->
    typename enable_if<!is_same<n, string>::value,
                       decltype(y.begin(), p)>::type {
  int o = 0;
  p << "{";
  for (auto c : y) {
    if (o++) p << ", ";
    p << c;
  }
  return p << "}";
}
void dor() { cerr << '\n'; }
template <class n, class... second>
void dor(n p, second... y) {
  cerr << p << " ";
  dor(y...);
}
template <class n, class second>
void mini(n &p, second y) {
  if (p > y) p = y;
}
template <class n, class second>
void maxi(n &p, second y) {
  if (p < y) p = y;
}
const int MXN = 3e5 + 5;
const int lg = 19;
int in[MXN];
const int BASE = 1 << lg;
int t[lg][BASE * 2];
int t2[lg][BASE * 2];
void insert_max(int j, int i, int x) {
  i += BASE;
  t[j][i] = x;
  i /= 2;
  while (i) {
    t[j][i] = max(t[j][i * 2], t[j][i * 2 + 1]);
    i /= 2;
  }
}
int query_max(int j, int a, int b) {
  a += BASE - 1;
  b += BASE + 1;
  int r = 0;
  while (a / 2 != b / 2) {
    if (a % 2 == 0) maxi(r, t[j][a + 1]);
    if (b % 2 == 1) maxi(r, t[j][b - 1]);
    a /= 2;
    b /= 2;
  }
  return r;
}
void insert_min(int j, int i, int x) {
  i += BASE;
  t2[j][i] = x;
  i /= 2;
  while (i) {
    t2[j][i] = min(t2[j][i * 2], t2[j][i * 2 + 1]);
    i /= 2;
  }
}
int query_min(int j, int a, int b) {
  a += BASE - 1;
  b += BASE + 1;
  int r = 1e9;
  while (a / 2 != b / 2) {
    if (a % 2 == 0) mini(r, t2[j][a + 1]);
    if (b % 2 == 1) mini(r, t2[j][b - 1]);
    a /= 2;
    b /= 2;
  }
  return r;
}
pair<int, int> que(int j, int a, int b) {
  return make_pair(query_min(j, a, b), query_max(j, a, b));
}
int main() {
  int n;
  scanf("%d", &n);
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (int i = (1); i <= (int)(n); ++i) {
    scanf("%d", &in[i]);
    in[i + n * 2] = in[i + n] = in[i];
  }
  for (int i = (1); i <= (int)(3 * n); ++i) {
    insert_min(0, i, (max(1, i - in[i])));
    insert_max(0, i, (min(3 * n, i + in[i])));
  }
  for (int i = (1); i <= (int)(lg - 1); ++i) {
    for (int j = (1); j <= (int)(3 * n); ++j) {
      pair<int, int> x = que(i - 1, j, j);
      pair<int, int> y = que(i - 1, x.first, x.second);
      insert_min(i, j, y.first);
      insert_max(i, j, y.second);
    }
  }
  for (int i = (n + 1); i <= (int)(2 * n); ++i) {
    int res = 0;
    int pra_i = i;
    int lew_i = i;
    for (int j = (lg - 1); j >= (int)(0); --j) {
      pair<int, int> x = que(j, lew_i, pra_i);
      if (x.second - x.first + 1 >= n) {
      } else {
        pra_i = x.second;
        lew_i = x.first;
        res += 1 << j;
      }
    }
    printf("%d ", res + 1);
  }
}
