Nearest Opposite Parity

Problem Description

Given an array $a$ of length $n$ indexed from $1$. From position $i$ you can move to position $i - a_i$ (if $1 \le i - a_i$) or $i + a_i$ (if $i + a_i \le n$).

For each position $i$ ($1 \le i \le n$), find the minimum number of steps to reach some position $j$ such that $a_i \bmod 2 \neq a_j \bmod 2$. If no such position $j$ exists, output -1.

Input Format

The first line contains an integer $n$ ($1 \le n \le 2 \times 10^5$), the length of the array.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le n$), the given array.

Output Format

Output one line containing $n$ integers, where the $j$-th integer is the answer starting from position $j$.

Sample Input

10
4 5 7 6 7 5 4 4 6 4

Sample Output

1 1 1 2 -1 1 1 3 1 1