最近相反点

题目描述

小核桃来到了一个神奇的国度。

这个国度有一条长长的路，路上有 $n$ 个标记了数字的石头，编号分别为 $1$ 到 $n$。 每个石头上都刻有一个数字 $a_i$，代表站在该石头上的小核桃能够向前或向后跳跃 $a_i$ 个距离，即可以到达编号为 $i - a_i$ 和 $i + a_i$ 的石头。

小核桃有一个特别的习惯：它喜欢在奇偶性不同的石头之间跳跃。

每当他站在一个编号为 $i$ 的石头上时，如果 $a_i$ 为奇数，他就会尽快跳到石头 $j$ 上，使得 $a_j$ 为偶数；同样的，当 $a_i$ 为偶数时，他也会尽快跳到一个编号为 $j$ 的石头上，使得 $a_j$ 为奇数。

为了满足这个习惯，小核桃希望知道从它所在的任意一个石头出发，至少需要跳跃几次才能到达最近的一个具有不同奇偶性的石头。

输入格式

第一行一个整数 $n$，表示石头的个数。

第二行 $n$ 个整数 $a_1,a_2, \cdots ,a_n$，表示每个石头上的数字。

输出格式

一行 $n$ 个整数 $d_1,d_2, \cdots ,d_n$，表示在编号为 $i$ 的石头上，至少要跳 $d_i$ 次，才能跳到一个奇偶性不同的石头上。

如果不能到达这样的位置，输出 $−1$。

样例 #1

样例输入 #1

10
4 5 7 6 7 5 4 4 6 4

样例输出 #1

1 1 1 2 -1 1 1 3 1 1

数据范围

$1 \le n \le 2 \cdot 10^5$，$1 \le a_i \le n$。

提示

对于编号为 $i$ 的石头，可以考虑在 $i$ 与 $i - a_i$，以及 $i$ 与 $i + a_i$ 之间建边。