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 <class T1, class T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &rhs) {
  out << "( " << rhs.first << " , " << rhs.second << " )";
  return out;
}
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
using ll = int64_t;
using ld = long double;
const ld EPS = 1e-11;
const ll MOD = 998244353;
const ld PI = 3.141592653589793;
const int maxn = 3e5 + 1;
int dp[17][2][maxn];
int t_dp[17][2][4 * maxn];
void build_mx(int v, int tl, int tr, int *a, int *where) {
  if (tl == tr - 1) {
    where[v] = a[tl];
    return;
  }
  int tm = (tl + tr) >> 1;
  build_mx(v << 1, tl, tm, a, where);
  build_mx(v << 1 | 1, tm, tr, a, where);
  where[v] = max(where[v << 1], where[v << 1 | 1]);
}
int get_mx(int v, int tl, int tr, int l, int r, int *where) {
  if (tl >= r || l >= tr) {
    return -1;
  }
  if (tl >= l && tr <= r) {
    return where[v];
  }
  int tm = (tl + tr) >> 1;
  return max(get_mx(v << 1, tl, tm, l, r, where),
             get_mx(v << 1 | 1, tm, tr, l, r, where));
}
void build_mn(int v, int tl, int tr, int *a, int *where) {
  if (tl == tr - 1) {
    where[v] = a[tl];
    return;
  }
  int tm = (tl + tr) >> 1;
  build_mn(v << 1, tl, tm, a, where);
  build_mn(v << 1 | 1, tm, tr, a, where);
  where[v] = min(where[v << 1], where[v << 1 | 1]);
}
int get_mn(int v, int tl, int tr, int l, int r, int *where) {
  if (tl >= r || l >= tr) {
    return 1e9;
  }
  if (tl >= l && tr <= r) {
    return where[v];
  }
  int tm = (tl + tr) >> 1;
  return min(get_mn(v << 1, tl, tm, l, r, where),
             get_mn(v << 1 | 1, tm, tr, l, r, where));
}
vector<int> clever(vector<int> xx) {
  int n = xx.size();
  vector<int> r(3 * n);
  for (int i = 0; i < n; ++i) {
    r[i] = xx[i];
    r[n + i] = r[i];
    r[2 * n + i] = r[i];
  }
  if (n == 1) {
    return {0};
  }
  for (int i = n; i < 2 * n; ++i) {
    dp[0][0][i] = i - r[i];
    dp[0][1][i] = i + r[i];
    dp[0][0][n + i] = min(n + dp[0][0][i], 3 * n - 1);
    dp[0][1][n + i] = min(n + dp[0][1][i], 3 * n - 1);
    dp[0][0][i - n] = max(0, dp[0][0][i] - n);
    dp[0][1][i - n] = max(0, dp[0][1][i] - n);
  }
  for (int step = 1; step < 17; ++step) {
    build_mn(1, 0, 3 * n, dp[step - 1][0], t_dp[step - 1][0]);
    build_mx(1, 0, 3 * n, dp[step - 1][1], t_dp[step - 1][1]);
    for (int i = n; i < 2 * n; ++i) {
      int l = dp[step - 1][0][i];
      int r = dp[step - 1][1][i];
      dp[step][0][i] = get_mn(1, 0, 3 * n, l, r + 1, t_dp[step - 1][0]);
      dp[step][1][i] = get_mx(1, 0, 3 * n, l, r + 1, t_dp[step - 1][1]);
      dp[step][0][i - n] = max(0, dp[step][0][i] - n);
      dp[step][1][i - n] = dp[step][1][i] - n;
      dp[step][0][i + n] = dp[step][0][i] + n;
      dp[step][1][i + n] = min(dp[step][1][i] + n, 3 * n - 1);
    }
  }
  build_mn(1, 0, 3 * n, dp[16][0], t_dp[16][0]);
  build_mx(1, 0, 3 * n, dp[16][1], t_dp[16][1]);
  vector<int> ans;
  for (int i = n; i < 2 * n; ++i) {
    int lpos = i;
    int rpos = i;
    int sum = 1;
    int need = 0;
    for (int bt = 16; bt >= 0; --bt) {
      int cur_lft = get_mn(1, 0, 3 * n, lpos, rpos + 1, t_dp[bt][0]);
      int cur_rgt = get_mx(1, 0, 3 * n, lpos, rpos + 1, t_dp[bt][1]);
      int cur_sum = cur_rgt - cur_lft + 1;
      if (cur_sum < n) {
        sum = cur_sum;
        need ^= (1 << bt);
        lpos = cur_lft;
        rpos = cur_rgt;
      }
    }
    ans.push_back(need + 1);
  }
  return ans;
}
vector<int> dumb(vector<int> xx) {
  int n = xx.size();
  vector<int> ans(n);
  for (int i = 0; i < n; ++i) {
    int tm = 0;
    int l = i;
    int r = i;
    while (r - l + 1 < n) {
      int mn = 1e9;
      int mx = -1e9;
      for (int i = l; i <= r; ++i) {
        mn = min(mn, i - xx[(n + i) % n]);
        mx = max(mx, i + xx[(n + i) % n]);
      }
      ++tm;
      l = mn;
      r = mx;
    }
    ans[i] = tm;
  }
  return ans;
}
void stress() {
  int n;
  mt19937 mt(232312);
  uniform_int_distribution<> un(10, 20);
  for (int it = 1;; ++it) {
    42;
    n = un(mt);
    uniform_int_distribution<> un_r(1, n);
    vector<int> xx(n);
    for (auto &el : xx) {
      el = un_r(mt);
    }
    auto clv = clever(xx);
    auto dmb = dumb(xx);
    if (clv != dmb) {
      42;
      42;
      42;
      42;
      exit(1);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cout.precision(10);
  cout << fixed;
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> r(n);
  for (int i = 1; i <= n; ++i) {
    cin >> r[i - 1];
  }
  auto ans = clever(r);
  for (int el : ans) {
    cout << el << " ";
  }
}
