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 N = 3e5 + 7;
int a[N];
int ans[N];
struct Seg {
  static const int N = ::N << 2;
  int Max[N], Min[N];
  int L[::N], R[::N];
  void build(int l, int r, int node) {
    if (l == r) {
      Min[node] = L[l], Max[node] = R[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, node << 1);
    build(mid + 1, r, node << 1 | 1);
    Min[node] = min(Min[node << 1], Min[node << 1 | 1]);
    Max[node] = max(Max[node << 1], Max[node << 1 | 1]);
  }
  int qmax(int l, int r, int node, int L, int R) {
    if (L <= l && r <= R) return Max[node];
    int mid = (l + r) >> 1, ans = 0;
    if (L <= mid) ans = max(ans, qmax(l, mid, node << 1, L, R));
    if (R > mid) ans = max(ans, qmax(mid + 1, r, node << 1 | 1, L, R));
    return ans;
  }
  int qmin(int l, int r, int node, int L, int R) {
    if (L <= l && r <= R) return Min[node];
    int mid = (l + r) >> 1, ans = N;
    if (L <= mid) ans = min(ans, qmin(l, mid, node << 1, L, R));
    if (R > mid) ans = min(ans, qmin(mid + 1, r, node << 1 | 1, L, R));
    return ans;
  }
} seg[18];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = (1); i < (3 * n + 1); ++i) {
    if (i <= n)
      scanf("%d", &a[i]);
    else
      a[i] = a[i - n];
    seg[0].L[i] = max(1, i - a[i]);
    seg[0].R[i] = min(3 * n, i + a[i]);
  }
  if (n == 1) {
    puts("0");
    return 0;
  }
  for (int i = (1); i < (18); ++i) {
    seg[i - 1].build(1, 3 * n, 1);
    for (int j = (1); j < (3 * n + 1); ++j) {
      seg[i].L[j] =
          seg[i - 1].qmin(1, 3 * n, 1, seg[i - 1].L[j], seg[i - 1].R[j]);
      seg[i].R[j] =
          seg[i - 1].qmax(1, 3 * n, 1, seg[i - 1].L[j], seg[i - 1].R[j]);
    }
  }
  for (int j = (1); j < (n + 1); ++j) {
    int res = 0, nowl = j + n, nowr = j + n;
    for (int i = (17) - 1; i >= (0); --i) {
      int nxtl = seg[i].qmin(1, 3 * n, 1, nowl, nowr);
      int nxtr = seg[i].qmax(1, 3 * n, 1, nowl, nowr);
      if (nxtr - nxtl + 1 < n) {
        res += (1 << i);
        nowl = nxtl;
        nowr = nxtr;
      }
      ans[j] = res + 1;
    }
  }
  for (int i = (1); i < (n + 1); ++i) printf("%d%c", ans[i], " \n"[i == n]);
  return 0;
}
