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 = 1000000007;
const int INF = 1000000001;
template <typename Compare>
struct SegmentTree {
  int n;
  vector<int> seg, a;
  Compare cmp;
  SegmentTree(int n, const Compare &cmp) : n(n), cmp(cmp) { a.resize(2 * n); }
  void build() {
    for (int i = n - 1; i > 0; i--)
      a[i] = cmp(a[i * 2], a[i * 2 + 1]) ? a[i * 2] : a[i * 2 + 1];
  }
  void modify(int v, int s) {
    for (a[v += n] = s; v /= 2;)
      a[v] = cmp(a[v * 2], a[v * 2 + 1]) ? a[v * 2] : a[v * 2 + 1];
  }
  int get(int l, int r) {
    int result = INF;
    if (cmp(result, 0)) result *= -1;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) {
        result = cmp(result, a[l]) ? result : a[l];
        l++;
      }
      if (r & 1) {
        r--;
        result = cmp(result, a[r]) ? result : a[r];
      }
    }
    return result;
  }
};
int n, r[100005], a[300005];
vector<SegmentTree<less<int>>> mn;
vector<SegmentTree<greater<int>>> mx;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> r[i];
  int lg = log2(n) + 1;
  mn.resize(lg, SegmentTree<less<int>>(3 * n, less<int>()));
  mx.resize(lg, SegmentTree<greater<int>>(3 * n, greater<int>()));
  for (int i = 0; i < 3 * n; i++) {
    a[i] = r[i % n];
    mn[0].a[i + mn[0].n] = max(0, i - a[i]);
    mx[0].a[i + mx[0].n] = min(3 * n - 1, i + a[i]);
  }
  mn[0].build();
  mx[0].build();
  for (int i = 1; i < lg; i++) {
    for (int j = 0; j < 3 * n; j++) {
      int L = mn[i - 1].get(j, j + 1);
      int R = mx[i - 1].get(j, j + 1);
      mn[i].a[j + mn[i].n] = mn[i - 1].get(L, R + 1);
      mx[i].a[j + mx[i].n] = mx[i - 1].get(L, R + 1);
    }
    mn[i].build();
    mx[i].build();
  }
  for (int i = n; i < 2 * n; i++) {
    int result = 0, l = i, r = i;
    for (int j = lg - 1; j > -1; j--) {
      int nl = mn[j].get(l, r + 1);
      int nr = mx[j].get(l, r + 1);
      if (nr - nl <= n - 1) {
        l = nl;
        r = nr;
        result += 1 << j;
      }
    }
    cout << result + (r - l < n - 1) << " ";
  }
  cout << "\n"
       << "\n";
  return 0;
}
