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>
const int N = 300005, LG = 19;
int n, d[N];
int Log[N];
struct Node {
  int l, r;
} a[N][LG];
struct ST {
  int st[N][LG];
  std::function<int(int, int)> val;
  template <typename func>
  ST(func _val) {
    val = _val;
  }
  void init() {
    for (int i = 1; i <= 3 * n; ++i) {
      st[i][0] = i;
    }
    for (int j = 1; j < LG; ++j) {
      for (int i = 1; i <= 3 * n - (1 << j) + 1; ++i) {
        st[i][j] = val(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  int query(int l, int r) {
    int t = Log[r - l + 1];
    return val(st[l][t], st[r - (1 << t) + 1][t]);
  }
};
ST L([](int x, int y) { return a[x][0].l < a[y][0].l ? x : y; }),
    R([](int x, int y) { return a[x][0].r > a[y][0].r ? x : y; });
Node trans(const Node &now, int k) {
  Node res;
  int pl = L.query(now.l, now.r);
  int pr = R.query(now.l, now.r);
  res.l = std::min(a[pl][k].l, a[pr][k].l);
  res.r = std::max(a[pl][k].r, a[pr][k].r);
  return res;
}
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cin >> n;
  for (int i = n + 1; i <= 2 * n; ++i) {
    std::cin >> d[i];
    d[i - n] = d[i + n] = d[i];
  }
  if (n == 1) {
    std::cout << 0 << "\n";
    return 0;
  }
  Log[1] = 0;
  for (int i = 2; i <= 3 * n; ++i) {
    Log[i] = Log[i >> 1] + 1;
  }
  for (int i = 1; i <= 3 * n; ++i) {
    a[i][0].l = std::max(1, i - d[i]);
    a[i][0].r = std::min(3 * n, i + d[i]);
  }
  L.init(), R.init();
  for (int j = 1; j < LG; ++j) {
    for (int i = 1; i <= 3 * n; ++i) {
      a[i][j] = trans(a[i][j - 1], j - 1);
    }
  }
  for (int i = n + 1; i <= 2 * n; ++i) {
    Node now;
    now.l = now.r = i;
    int ans = 0;
    for (int j = LG - 1; ~j; --j) {
      Node tr = trans(now, j);
      if (tr.r - tr.l + 1 < n) {
        now = tr;
        ans += 1 << j;
      }
    }
    std::cout << ans + 1 << " ";
  }
  std::cout << "\n";
}
