CF1272E · Nearest Opposite Parity

• 难度：1900
• 标签：dfs and similar、graphs、shortest paths
• 链接：https://codeforces.com/problemset/problem/1272/E
• 时间限制：2 seconds　内存限制：256 megabytes
• 出现位置：Day28-阶段模拟7-S T1-T3综合卷

英文原题面

Statement

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 \le i - a_i$) or to the position $i + a_i$ (if $i + a_i \le 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 \le n \le 2 \cdot 10^5$) — the number of elements in $a$. The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the $i$-th element of $a$.

Output

Print $n$ integers $d_1, d_2, \dots, 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.

样例

样例 1

输入：

10
4 5 7 6 7 5 4 4 6 4

输出：

1 1 1 2 -1 1 1 3 1 1