奇偶跳跃

题目描述

Y 同学得到了一个长度为 $N$ 的整数序列 $A = \{a_1, a_2, \dots, a_N\}$。

当他位于序列的第 $i$ 个位置（$1 \le i \le N$）时，他可以执行一次跳跃。跳跃的目标位置可以是 $i - a_i$ 或者 $i + a_i$，但前提是目标位置必须在序列的有效范围内（即下标必须在 $[1, N]$ 之间）。

对于序列中的每一个位置 $i$，Y 同学希望计算出：从位置 $i$ 出发，最少需要经过多少次跳跃，才能到达一个位置 $j$，使得 $a_j$ 的奇偶性与 $a_i$ 不同（即 $a_i \not\equiv a_j \pmod 2$）。

如果对于某个位置 $i$，无法到达任何满足条件的位置，则记为 $-1$。

输入格式

第一行输入一个正整数 $N$，表示序列的长度。

第二行输入 $N$ 个正整数 $a_1, a_2, \dots, a_N$，表示序列中的元素。

输出格式

输出一行 $N$ 个整数，第 $i$ 个整数表示从位置 $i$ 出发到达奇偶性不同的位置所需的最少步数。如果无法到达，输出 $-1$。

样例

样例输入 #1

10
4 5 7 6 7 5 4 4 6 4

样例输出 #1

1 1 1 2 -1 1 1 3 1 1 

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le N \le 2 \times 10^5$
• $1 \le a_i \le N$