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 sz = 3e5 + 10, inf = 1e9;
int ll[16][sz], rr[16][sz], dot[16][sz * 4][2];
void build(int i, int nu, int l, int r) {
  if (l == r) {
    dot[i][nu][0] = ll[i][l];
    dot[i][nu][1] = rr[i][r];
  } else {
    int mid = (l + r) >> 1;
    build(i, nu * 2, l, mid);
    build(i, nu * 2 + 1, mid + 1, r);
    dot[i][nu][0] = min(dot[i][nu * 2][0], dot[i][nu * 2 + 1][0]);
    dot[i][nu][1] = max(dot[i][nu * 2][1], dot[i][nu * 2 + 1][1]);
  }
}
int lg, rg;
pair<int, int> que(int i, int nu, int l, int r) {
  if (l >= lg and r <= rg)
    return {dot[i][nu][0], dot[i][nu][1]};
  else if (l > rg or r < lg)
    return {inf, -inf};
  else {
    int mid = (l + r) >> 1;
    pair<int, int> lva = que(i, nu * 2, l, mid),
                   rva = que(i, nu * 2 + 1, mid + 1, r);
    return {min(lva.first, rva.first), max(lva.second, rva.second)};
  }
}
int main() {
  int n;
  cin >> n;
  for (int a = 0; a < n; a++) {
    int q;
    scanf("%d", &q);
    for (int i = 0; i < 3; i++) {
      ll[0][i * n + a] = max(0, i * n + a - q);
      rr[0][i * n + a] = min(n * 3 - 1, i * n + a + q);
    }
  }
  build(0, 1, 0, n * 3);
  for (int i = 1; i < 16; i++) {
    for (int a = 0; a < n * 3; a++) {
      lg = ll[i - 1][a], rg = rr[i - 1][a];
      pair<int, int> re = que(i - 1, 1, 0, n * 3);
      ll[i][a] = re.first, rr[i][a] = re.second;
    }
    build(i, 1, 0, n * 3);
  }
  for (int a = 0; a < n; a++) {
    int cl = n + a, cr = n + a, su = 0;
    for (int i = 15; i >= 0; i--) {
      lg = cl, rg = cr;
      pair<int, int> re = que(i, 1, 0, n * 3);
      if (re.second - re.first + 1 < n) {
        cl = re.first, cr = re.second, su += (1 << i);
      }
    }
    if (cr - cl + 1 < n) su++;
    printf("%d ", su);
  }
}
