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;
int a[100001], lg[(3 * 100001)], leftEnd[(3 * 100001)], rightEnd[(3 * 100001)],
    ans[(3 * 100001)], leftEndTable[19][(3 * 100001)],
    rightEndTable[19][(3 * 100001)], leftEndSparseTable[19][(3 * 100001)],
    rightEndSparseTable[19][(3 * 100001)];
void BuildSparseTables(int n, int k) {
  for (int i = 0; i < n; ++i) {
    leftEndSparseTable[0][i] = leftEndTable[k][i];
    rightEndSparseTable[0][i] = rightEndTable[k][i];
  }
  for (int k = 1; k < 19; ++k) {
    for (int i = 0, j = (1 << (k - 1)); j < n; ++i, ++j) {
      leftEndSparseTable[k][i] =
          min(leftEndSparseTable[k - 1][i], leftEndSparseTable[k - 1][j]);
      rightEndSparseTable[k][i] =
          max(rightEndSparseTable[k - 1][i], rightEndSparseTable[k - 1][j]);
    }
  }
}
int LeftEndRMQ(int i, int j) {
  int k = lg[j - i + 1];
  return min(leftEndSparseTable[k][i],
             leftEndSparseTable[k][(j - (1 << k) + 1)]);
}
int RightEndRMQ(int i, int j) {
  int k = lg[j - i + 1];
  return max(rightEndSparseTable[k][i],
             rightEndSparseTable[k][(j - (1 << k) + 1)]);
}
void Initialize(int n, int m) {
  for (int i = 2; i <= m; ++i) {
    lg[i] = 1 + lg[(i / 2)];
  }
  for (int i = 0; i < m; ++i) {
    leftEndTable[0][i] = max(0, i - a[(i % n)]);
    rightEndTable[0][i] = min(m - 1, i + a[(i % n)]);
  }
}
void PreProcess(int m) {
  for (int k = 1; k < 19; ++k) {
    BuildSparseTables(m, k - 1);
    for (int i = 0; i < m; ++i) {
      leftEndTable[k][i] =
          LeftEndRMQ(leftEndTable[k - 1][i], rightEndTable[k - 1][i]);
      rightEndTable[k][i] =
          RightEndRMQ(leftEndTable[k - 1][i], rightEndTable[k - 1][i]);
    }
  }
}
void Solve(int n, int m) {
  for (int i = 0; i < m; ++i) {
    leftEnd[i] = i;
    rightEnd[i] = i;
  }
  for (int k = 19 - 1; k > -1; --k) {
    BuildSparseTables(m, k);
    for (int i = 0; i < m; ++i) {
      int l = LeftEndRMQ(leftEnd[i], rightEnd[i]),
          r = RightEndRMQ(leftEnd[i], rightEnd[i]);
      if (r - l + 1 < n) {
        ans[i] += (1 << k);
        leftEnd[i] = l;
        rightEnd[i] = r;
      }
    }
  }
}
int main() {
  int n;
  scanf("%d", &n);
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  int m = 3 * n;
  Initialize(n, m);
  PreProcess(m);
  Solve(n, m);
  for (int i = n; i < 2 * n; ++i) {
    printf("%d ", 1 + ans[i]);
  }
  printf("\n");
  return 0;
}
