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 long long MAXN = 3e5 + 10;
long long N, M, Log[MAXN], val[MAXN], lb[MAXN], rb[MAXN], lt[21][MAXN],
    rt[21][MAXN];
struct st_biao {
  long long st[21][MAXN], v[MAXN], type;
  long long Max(long long x, long long y) { return (v[x] < v[y]) ? y : x; }
  void build(long long *now, long long n, long long _type) {
    type = _type;
    for (long long i = 1; i <= n; i++) st[0][i] = i, v[i] = type * now[i];
    for (long long i = 1; i <= Log[n]; i++)
      for (long long j = 1; j + (1LL << i) - 1 <= n; j++)
        st[i][j] = Max(st[i - 1][j], st[i - 1][j + (1LL << (i - 1))]);
  }
  long long qmin(long long l, long long r) {
    long long dis = Log[r - l + 1];
    return Max(st[dis][l], st[dis][r - (1LL << dis) + 1]);
  }
} stl, str;
int main() {
  scanf("%lld", &N);
  for (long long i = 2; i <= 3 * N; i++) Log[i] = Log[i >> 1] + 1;
  for (long long i = 1; i <= N; i++)
    scanf("%lld", val + i), val[i + N * 2] = val[i + N] = val[i];
  if (N == 1) {
    puts("0");
    return 0;
  }
  for (long long i = 1; i <= 3 * N; i++) {
    lb[i] = max(1LL, i - val[i]);
    rb[i] = min(3 * N, i + val[i]);
  }
  for (long long i = 0; i <= Log[3 * N]; i++)
    rt[i][3 * N] = 3 * N, lt[i][1] = 1;
  for (long long i = 1; i <= 3 * N; i++) {
    lt[0][i] = lb[i];
    rt[0][i] = rb[i];
  }
  stl.build(lt[0], 3 * N, -1), str.build(rt[0], 3 * N, 1);
  for (long long i = 1; i <= Log[3 * N]; i++) {
    for (long long j = 1; j <= 3 * N; j++) {
      long long pl = stl.qmin(lt[i - 1][j], rt[i - 1][j]);
      long long pr = str.qmin(lt[i - 1][j], rt[i - 1][j]);
      lt[i][j] = min(lt[i - 1][pl], lt[i - 1][pr]);
      rt[i][j] = max(rt[i - 1][pl], rt[i - 1][pr]);
    }
  }
  for (long long j = N + 1; j <= 2 * N; j++) {
    long long ans = 0;
    long long lk = j, rk = j;
    for (long long i = Log[3 * N]; ~i; i--) {
      if (max(rt[i][lk], rt[i][rk]) - min(lt[i][lk], lt[i][rk]) + 1 >= N)
        continue;
      long long nl = stl.qmin(lt[i][lk], rt[i][rk]);
      long long nr = str.qmin(lt[i][lk], rt[i][rk]);
      lk = nl, rk = nr;
      ans += (1LL << i);
    }
    printf("%lld ", ans + 1);
  }
  return 0;
}
