题目描述

有一条编号为 $1$ 到 $n$ 的跳格道路，第 $i$ 个格子上写着一个整数 $a_i$。

当你站在第 $i$ 个格子上时，最多可以选择下面两种跳法：

• 跳到第 $i-a_i$ 个格子；
• 跳到第 $i+a_i$ 个格子。

如果目标位置不在 $1$ 到 $n$ 的范围内，则这种跳法不能使用。

现在，对于每一个起点 $i$，你需要求出：最少跳多少步，才能到达某个格子 $j$，使得 $a_j$ 和 $a_i$ 的奇偶性不同。

如果从位置 $i$ 出发，无论怎样跳都无法到达这样的格子，则输出 $-1$。

输入格式

第一行输入一个整数 $n$，表示格子数量。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个格子上的数字。

输出格式

输出一行 $n$ 个整数 $d_1,d_2,\ldots,d_n$。

其中 $d_i$ 表示从第 $i$ 个格子出发，到达一个数字奇偶性与 $a_i$ 不同的格子所需的最少步数。

如果无法到达，输出 $-1$。

样例

10
4 5 7 6 7 5 4 4 6 4

1 1 1 2 -1 1 1 3 1 1

样例1解释

以第 $4$ 个格子为例，$a_4=6$，是偶数。

可以这样跳：

4 -> 10 -> 6

第 $6$ 个格子上的数字为 $5$，是奇数，与 $a_4$ 奇偶性不同，因此第 $4$ 个格子的答案为 $2$。

第 $5$ 个格子无法跳到任何奇偶性不同的格子，因此答案为 $-1$。

数据范围

对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$，$1 \le a_i \le n$。