You are given an array a consisting of n integers. In one move, you can jump from the position i to the position i - a_i (if 1 ≤ i - a_i) or to the position i + a_i (if i + a_i ≤ n).

For each position i from 1 to n you want to know the minimum the number of moves required to reach any position j such that a_j has the opposite parity from a_i (i.e. if a_i is odd then a_j has to be even and vice versa).

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of elements in a.

The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n), where a_i is the i-th element of a.

Output

Print n integers d_1, d_2, ..., d_n, where d_i is the minimum the number of moves required to reach any position j such that a_j has the opposite parity from a_i (i.e. if a_i is odd then a_j has to be even and vice versa) or -1 if it is impossible to reach such a position.

Example

Input


10
4 5 7 6 7 5 4 4 6 4


Output


1 1 1 2 -1 1 1 3 1 1 
#include <bits/stdc++.h>
using namespace std;
template <class T>
constexpr T lcm(T m, T n) {
  return m / __gcd(m, n) * n;
}
template <typename I>
void join(ostream &ost, I s, I t, string d = " ") {
  for (auto i = s; i != t; ++i) {
    if (i != s) ost << d;
    ost << *i;
  }
  ost << endl;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &a : v) is >> a;
  return is;
}
template <typename T, typename U>
bool chmin(T &a, const U &b) {
  return (a > b ? a = b, true : false);
}
template <typename T, typename U>
bool chmax(T &a, const U &b) {
  return (a < b ? a = b, true : false);
}
template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v) {
  fill((U *)a, (U *)(a + N), v);
}
struct Init {
  Init() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
} init;
template <typename Cost = int>
class Edge {
 public:
  int from, to;
  Cost cost;
  Edge() {}
  Edge(int to, Cost cost) : to(to), cost(cost) {}
  Edge(int from, int to, Cost cost) : from(from), to(to), cost(cost) {}
  Edge rev() const { return Edge(to, from, cost); }
  friend std::ostream &operator<<(std::ostream &os, const Edge &e) {
    os << "(FROM: " << e.from << ","
       << "TO: " << e.to << ","
       << "COST: " << e.cost << ")";
    return os;
  }
};
template <typename T>
using Graph = std::vector<std::vector<Edge<T>>>;
template <typename T>
using Tree = std::vector<std::vector<Edge<T>>>;
template <typename C, typename T>
void add_edge(C &g, int from, int to, T w) {
  g[from].push_back(Edge<T>(from, to, w));
}
template <typename C, typename T>
void add_undirected(C &g, int a, int b, T w) {
  g[a].push_back(Edge<T>(a, b, w));
  g[b].push_back(Edge<T>(b, a, w));
}
template <typename T>
vector<int> bfs_shortest_path(const Graph<T> &g, const vector<int> &src) {
  int n = g.size();
  vector<int> ret(n, -1);
  vector<bool> visited(n);
  for (auto s : src) {
    ret[s] = 0;
  }
  queue<int> q;
  for (auto s : src) q.push(s);
  while (not q.empty()) {
    int cur = q.front();
    q.pop();
    if (visited[cur]) continue;
    visited[cur] = true;
    for (auto &e : g[cur]) {
      if (ret[e.to] == -1 or ret[e.to] > ret[e.from] + 1) {
        ret[e.to] = ret[e.from] + 1;
        q.push(e.to);
      }
    }
  }
  return ret;
}
int main() {
  int n;
  while (cin >> n) {
    vector<int> a(n);
    cin >> a;
    Graph<int> g(n);
    for (long long int i = (0); i < (n); ++i) {
      if (i - a[i] >= 0) add_edge(g, i - a[i], i, 1);
      if (i + a[i] < n) add_edge(g, i + a[i], i, 1);
    }
    vector<int> odd, even;
    for (long long int i = (0); i < (n); ++i) {
      if (a[i] % 2 == 0)
        even.push_back(i);
      else
        odd.push_back(i);
    }
    auto dist_odd = bfs_shortest_path(g, odd);
    auto dist_even = bfs_shortest_path(g, even);
    ((void)0);
    vector<int> ans(n);
    for (long long int i = (0); i < (n); ++i) {
      if (a[i] % 2 == 0) {
        ans[i] = dist_odd[i];
      } else {
        ans[i] = dist_even[i];
      }
    }
    join(cout, (ans).begin(), (ans).end());
  }
  return 0;
}
