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 mod = 1e9 + 7;
long long gcd(long long x, long long y) {
  while (y) x %= y, swap(x, y);
  return x;
}
pair<long long, long long> operator+(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return pair<long long, long long>(a.first + b.first, a.second + b.second);
}
pair<long long, long long> operator-(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return pair<long long, long long>(a.first - b.first, a.second - b.second);
}
long long operator*(pair<long long, long long> a,
                    pair<long long, long long> b) {
  return a.first * b.second - a.second * b.first;
}
template <class T>
int sign(T x) {
  return x < 0 ? -1 : x > 0 ? 1 : 0;
}
int ccw(pair<long long, long long> a, pair<long long, long long> b,
        pair<long long, long long> c) {
  return sign((b - a) * (c - b));
}
template <class T>
void setmin(T &x, T y) {
  if (x > y) x = y;
}
template <class T>
void setmax(T &x, T y) {
  if (x < y) x = y;
}
template <class T>
void addval(T &x, T y) {
  x += y;
  x %= mod;
}
size_t getCurrentTime() {
  return chrono::steady_clock::now().time_since_epoch().count();
}
struct __RandomLong__ {
  mt19937_64 rnd;
  __RandomLong__() : rnd(getCurrentTime()) {}
  long long operator()(long long Min, long long Max) {
    return uniform_int_distribution<long long>(Min, Max)(rnd);
  }
  long long operator()() { return (*this)(LONG_LONG_MIN, LONG_LONG_MAX); }
} randomLong;
struct my_hash {
  static uint64_t splitmix(uint64_t x) {
    x += 0x9e3779b97f4a7c15ull;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ull;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebull;
    return x ^ (x >> 31);
  }
  size_t operator()(long long x) const {
    static long long T = getCurrentTime();
    return splitmix(x + T);
  }
};
const pair<int, int> no = {-1, -1};
int n;
int R[100005];
pair<int, int> sm[20][100005];
pair<int, int> seg[20][400005];
pair<int, int> un(pair<int, int> x, pair<int, int> y) {
  if (x == no) return y;
  if (y == no) return x;
  if (x.first <= x.second && y.first <= y.second)
    return {min(x.first, y.first), max(x.second, y.second)};
  if (y.first <= y.second) swap(x, y);
  if (x.first <= x.second) {
    if (x.first <= y.second) y.second = max(y.second, x.second);
    if (y.first <= x.second) y.first = min(y.first, x.first);
    if (y.first <= y.second + 1) return {1, n};
    return y;
  }
  x.first = min(x.first, y.first);
  x.second = max(x.second, y.second);
  if (x.first <= x.second + 1) return {1, n};
  return x;
}
void init(int T, int i, int s, int e) {
  if (s == e) {
    seg[T][i] = sm[T][s];
    return;
  }
  int m = s + e >> 1;
  init(T, i * 2, s, m);
  init(T, i * 2 + 1, m + 1, e);
  seg[T][i] = un(seg[T][i * 2], seg[T][i * 2 + 1]);
}
pair<int, int> get(int T, int i, int s, int e, int x, int y) {
  if (e < x || y < s) return no;
  if (x <= s && e <= y) return seg[T][i];
  int m = s + e >> 1;
  return un(get(T, i * 2, s, m, x, y), get(T, i * 2 + 1, m + 1, e, x, y));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  if (n == 1) {
    cout << 0;
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    cin >> R[i];
    if (R[i] + R[i] + 1 >= n)
      sm[0][i] = {1, n};
    else
      sm[0][i] = {(i + n - R[i] - 1) % n + 1, (i + R[i] - 1) % n + 1};
  }
  init(0, 1, 1, n);
  for (int i = 1; i < 20; i++) {
    for (int j = 1; j <= n; j++) {
      pair<int, int> s = sm[i - 1][j];
      if (s.first <= s.second) {
        s = get(i - 1, 1, 1, n, s.first, s.second);
      } else {
        s = un(get(i - 1, 1, 1, n, s.first, n),
               get(i - 1, 1, 1, n, 1, s.second));
      }
      sm[i][j] = s;
    }
    init(i, 1, 1, n);
  }
  for (int i = 1; i <= n; i++) {
    pair<int, int> s = {i, i};
    int ans = 0;
    for (int j = 20; j--;) {
      pair<int, int> r;
      if (s.first <= s.second)
        r = get(j, 1, 1, n, s.first, s.second);
      else
        r = un(get(j, 1, 1, n, s.first, n), get(j, 1, 1, n, 1, s.second));
      if (r.first != 1 || r.second != n) {
        ans |= 1 << j;
        s = r;
      }
    }
    cout << ans + 1 << ' ';
  }
}
