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(3)
using namespace std;
template <typename T>
inline bool chkmin(T &x, T y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
inline void read(int &x) {
  char ch = getchar();
  int f = 1;
  x = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
int n, r[300050], ll[300050][22], rr[300050][22];
pair<int, int> res[300050 << 2][22];
inline int _max(int x, int y) { return x > y ? x : y; }
inline int _min(int x, int y) { return x < y ? x : y; }
pair<int, int> operator+(const pair<int, int> &x, const pair<int, int> &y) {
  return make_pair(_max(x.first, y.first), _min(x.second, y.second));
}
void build(int u, int l, int r, int d) {
  if (l == r) return (void)(res[u][d] = make_pair(rr[l][d], ll[l][d]));
  build(u << 1, l, ((l + r) >> 1), d),
      build(u << 1 | 1, ((l + r) >> 1) + 1, r, d);
  res[u][d] = res[u << 1][d] + res[u << 1 | 1][d];
}
pair<int, int> query(int u, int l, int r, int tl, int tr, int d) {
  if (tl <= l && r <= tr) return res[u][d];
  if (tr <= ((l + r) >> 1)) return query(u << 1, l, ((l + r) >> 1), tl, tr, d);
  if (((l + r) >> 1) < tl)
    return query(u << 1 | 1, ((l + r) >> 1) + 1, r, tl, tr, d);
  return query(u << 1, l, ((l + r) >> 1), tl, tr, d) +
         query(u << 1 | 1, ((l + r) >> 1) + 1, r, tl, tr, d);
}
int main() {
  read(n);
  if (n == 1) return cout << 0, 0;
  for (register int i = 1; i <= n; ++i)
    read(r[i + n]), r[i] = r[i + 2 * n] = r[i + n];
  for (register int i = 1; i <= n * 3; ++i)
    ll[i][0] = max(1, i - r[i]), rr[i][0] = min(n * 3, i + r[i]);
  build(1, 1, n * 3, 0);
  for (register int i = 1; i <= 19; ++i) {
    for (register int j = 1; j <= n * 3; ++j) {
      ll[j][i] = query(1, 1, n * 3, ll[j][i - 1], rr[j][i - 1], i - 1).second;
      rr[j][i] = query(1, 1, n * 3, ll[j][i - 1], rr[j][i - 1], i - 1).first;
    }
    build(1, 1, n * 3, i);
  }
  for (register int i = 1; i <= n; ++i) {
    int ans = 0;
    pair<int, int> cur = make_pair(i + n, i + n), nxt;
    for (register int j = 19; j >= 0; --j) {
      nxt = query(1, 1, n * 3, cur.second, cur.first, j);
      if (nxt.first - nxt.second + 1 < n) cur = nxt, ans += 1 << j;
    }
    printf("%d ", ans + 1);
  }
  return 0;
}
