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;
template <typename num_t>
inline void addmod(num_t& a, const long long& b, const int& m) {
  a = (a + b) % m;
  if (a < 0) a += m;
}
template <typename num_t>
inline void update_max(num_t& a, const num_t& b) {
  a = max(a, b);
}
template <typename num_t>
inline void update_min(num_t& a, const num_t& b) {
  a = min(a, b);
}
template <typename num_t>
num_t gcd(num_t lhs, num_t rhs) {
  return !lhs ? rhs : gcd(rhs % lhs, lhs);
}
template <typename num_t>
num_t pw(num_t n, num_t k, num_t mod) {
  long long res = 1;
  for (; k; k >>= 1) {
    if (k & 1) res = res * n % mod;
    n = 1ll * n * n % mod;
  }
  return (num_t)res;
}
const int inf = 1e9 + 7;
const long long ll_inf = 1ll * inf * inf;
const int MAX_N = 100000 + 7;
const int mod = 998244353;
template <typename num_t>
class SegmentTree {
 public:
  void init(int l, int r) {
    tree.resize((r - l + 1) << 1);
    queue.resize(tree.size());
    build_tree(l, r);
    initial_value.clear();
  }
  void init(const vector<num_t>& arr) {
    initial_value = arr;
    init(0, (int)arr.size() - 1);
  }
  void update(int left_index, int right_index, const num_t& val) {
    update_(left_index, right_index, val);
  }
  num_t get(int left_index, int right_index) {
    return tree[0].get(left_index, right_index);
  }

 private:
  struct node {
    static const num_t nil = inf;
    node *left_child, *right_child;
    int left_index, right_index;
    num_t value;
    void push_down(num_t v) { value = v; }
    void merge_node() {
      const node &lhs = *left_child, &rhs = *right_child;
      value = min(lhs.value, rhs.value);
    }
    void lazy_update() {}
    inline void init_value(num_t v = 0) { value = v; }
    num_t get(int u, int v) {
      if (u <= left_index && right_index <= v) return value;
      if (u > right_index || v < left_index) return node::nil;
      lazy_update();
      auto lhs = left_child->get(u, v);
      auto rhs = right_child->get(u, v);
      return min(lhs, rhs);
    }
    inline void init_index(int left, int right) {
      left_index = left;
      right_index = right;
    }
    inline void init_child(node* left, node* right) {
      left_child = left;
      right_child = right;
    }
    node() {}
    int size() const { return right_index - left_index + 1; }
  };
  vector<num_t> initial_value;
  vector<node> tree;
  vector<node*> queue;
  int node_index = 0;
  void build_tree(int left, int right) {
    node_index = 0;
    tree[node_index++].init_index(left, right);
    for (int j = 0; j < node_index; ++j) {
      node& root = tree[j];
      if (root.size() == 1) {
        if (!initial_value.empty())
          root.init_value(initial_value[root.left_index]);
        else
          root.init_value(0);
        root.init_child(nullptr, nullptr);
        continue;
      }
      int mid = (root.left_index + root.right_index) >> 1, lhs = node_index++,
          rhs = node_index++;
      root.init_child(&tree[lhs], &tree[rhs]);
      tree[lhs].init_index(root.left_index, mid);
      tree[rhs].init_index(mid + 1, root.right_index);
    }
    for (int j = node_index - 1; j >= 0; --j) {
      if (tree[j].size() > 1) tree[j].merge_node();
    }
  }
  void update_(int u, int v, const num_t& value) {
    int top = 0;
    queue[top++] = &tree[0];
    for (int j = 0; j < top; ++j) {
      node& root = *queue[j];
      if (u > root.right_index || v < root.left_index) continue;
      if (u <= root.left_index && root.right_index <= v) {
        root.push_down(value);
      } else {
        root.lazy_update();
        queue[top++] = root.left_child;
        queue[top++] = root.right_child;
      }
    }
    while (top > 0) {
      node& root = *queue[--top];
      if (root.size() > 1) root.merge_node();
    }
  }
};
template <typename num_t, const num_t& (*merge)(const num_t&, const num_t&)>
struct RMQ {
  int n;
  vector<vector<num_t>> rmq;
  void init(const vector<num_t>& arr) {
    n = (int)arr.size();
    build(arr);
  }
  void build(const vector<num_t>& arr) {
    rmq.clear();
    rmq.push_back(arr);
    for (int j = 1, max_j = n - (1 << j) + 1; max_j > 0; max_j -= 1 << j, j++) {
      rmq.push_back(vector<num_t>(max_j));
      for (int i = 0, half = 1 << (j - 1); i < max_j; ++i) {
        rmq[j][i] = merge(rmq[j - 1][i], rmq[j - 1][i + half]);
      }
    }
  }
  num_t get(int u, int v) {
    int k = log2(v - u + 1);
    return merge(rmq[k][u], rmq[k][v - (1 << k) + 1]);
  }
};
const int M = 18;
int prv[2][MAX_N];
int nxt[2][MAX_N];
SegmentTree<int> pre_left[M];
RMQ<int, std::max> pre_right[M];
int n;
int a[MAX_N];
int get_left(SegmentTree<int>& lhs, int u, int v) {
  if (u < 0) {
    u += n;
    v += n;
  }
  if (v < n) {
    return u - lhs.get(u, v);
  } else {
    int temp = 0;
    temp = max(temp, u - lhs.get(u, n - 1));
    temp = max(temp, u - (n + lhs.get(0, v - n)));
    return temp;
  }
}
int get_right(RMQ<int, std::max>& rhs, int u, int v) {
  if (u < 0) {
    u += n;
    v += n;
  }
  if (v < n) {
    return rhs.get(u, v) - v;
  } else {
    int temp = 0;
    temp = max(temp, rhs.get(u, n - 1) - v);
    temp = max(temp, rhs.get(0, v - n) + n - v);
    return temp;
  }
}
void init() {
  int cur = 0;
  for (int i = 0; i < n; ++i) {
    prv[cur][i] = i - a[i];
    nxt[cur][i] = i + a[i];
  }
  for (int j = 0; j < M; ++j) {
    if (j) {
      int pre = cur;
      cur ^= 1;
      for (int i = 0; i < n; ++i) {
        auto low = prv[pre][i], high = nxt[pre][i];
        if (high - low + 1 < n) {
          prv[cur][i] = low - get_left(pre_left[j - 1], low, high);
          nxt[cur][i] = high + get_right(pre_right[j - 1], low, high);
        } else {
          prv[cur][i] = low;
          nxt[cur][i] = high;
        }
      }
    }
    pre_left[j].init(vector<int>(prv[cur], prv[cur] + n));
    pre_right[j].init(vector<int>(nxt[cur], nxt[cur] + n));
  }
}
void solve() {
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> a[i];
  init();
  for (int i = 0; i < n; ++i) {
    int low = i, high = i;
    int res = 0;
    for (int j = M - 1; j >= 0 && high - low + 1 < n; --j) {
      if (low < 0) {
        low += n;
        high += n;
      };
      int new_low = low - get_left(pre_left[j], low, high);
      int new_high = high + get_right(pre_right[j], low, high);
      if (new_high - new_low + 1 < n) {
        res += 1 << j;
        low = new_low;
        high = new_high;
      }
    }
    if (high - low + 1 < n) ++res;
    cout << res << ' ';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}
