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 = 1e5 + 5;
int n;
typedef class Segment {
 public:
  int l, r;
  bool full;
  Segment() {}
  Segment(int l, int r, bool full = false) : l(l), r(r), full(full) {}
  friend Segment operator+(Segment a, Segment b) {
    if (a.full || b.full) {
      return Segment(0, n - 1, true);
    }
    if (a.l > a.r) a.r += n;
    if (b.l > b.r) b.r += n;
    if (a.r < b.l - 1) {
      assert(a.r < n);
      a.l += n, a.r += n;
    }
    if (b.r < a.l - 1) {
      assert(b.l < n);
      b.l += n, b.r += n;
    }
    assert(!(a.r < b.l - 1 || a.l > b.r + 1));
    Segment rt(min(a.l, b.l), max(a.r, b.r));
    if (rt.r - rt.l >= n - 1) rt.full = true;
    if (rt.l >= n && rt.r >= n) rt.l -= n, rt.r -= n;
    if (rt.r >= n) rt.r -= n;
    return rt;
  }
} Segment;
typedef class SegTreeNode {
 public:
  Segment seg;
  SegTreeNode *l, *r;
  void push_up() { seg = l->seg + r->seg; }
} SegTreeNode;
typedef class SegmentTree {
 public:
  static SegTreeNode pool[N * 40];
  static SegTreeNode* top;
  static SegTreeNode* newnode() {
    top->seg = Segment(0, 0);
    top->l = top->r = NULL;
    return top++;
  }
  int n;
  SegTreeNode* rt;
  SegmentTree() : rt(NULL) {}
  void build(SegTreeNode*& p, int l, int r, Segment* data) {
    p = newnode();
    if (l == r) {
      p->seg = data[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(p->l, l, mid, data);
    build(p->r, mid + 1, r, data);
    p->push_up();
  }
  void build(int n, Segment* data) {
    this->n = n;
    build(rt, 0, n - 1, data);
  }
  Segment query(SegTreeNode* p, int l, int r, int ql, int qr) {
    if (l == ql && r == qr) {
      return p->seg;
    }
    int mid = (l + r) >> 1;
    if (qr <= mid) {
      return query(p->l, l, mid, ql, qr);
    } else if (ql > mid) {
      return query(p->r, mid + 1, r, ql, qr);
    }
    return query(p->l, l, mid, ql, mid) + query(p->r, mid + 1, r, mid + 1, qr);
  }
  Segment query(int l, int r) {
    if (l <= r) {
      return query(rt, 0, n - 1, l, r);
    }
    return query(rt, 0, n - 1, l, n - 1) + query(rt, 0, n - 1, 0, r);
  }
} SegmentTree;
SegTreeNode SegmentTree ::pool[N * 40];
SegTreeNode* SegmentTree ::top = SegmentTree ::pool;
const int bzmax = 18;
int a[N];
Segment segs[N];
SegmentTree st[20];
int main() {
  scanf("%d", &n);
  if (n == 1) {
    puts("0");
    return 0;
  }
  int hn = n >> 1;
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    if (a[i] >= hn) {
      segs[i] = Segment(0, n - 1, true);
    } else {
      segs[i] = Segment((i - a[i] + n) % n, (i + a[i]) % n);
    }
  }
  st[0].build(n, segs);
  for (int i = 1; i < bzmax; i++) {
    for (int j = 0; j < n; j++) {
      if (!segs[j].full) {
        segs[j] = st[i - 1].query(segs[j].l, segs[j].r);
      }
    }
    st[i].build(n, segs);
  }
  for (int i = 0; i < n; i++) {
    int ans = 0;
    Segment cur(i, i), curn;
    for (int j = bzmax - 1; ~j; j--) {
      if (!(curn = st[j].query(cur.l, cur.r)).full) {
        ans |= (1 << j);
        cur = curn;
      }
    }
    printf("%d ", ans + 1);
  }
  return 0;
}
