A13123. Nearest Opposite Parity

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).

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$ .

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.