给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。一步操作中,您可以从位置 $$$i$$$ 跳转到位置 $$$i - a_i$$$(如果 $$$1 \le i - a_i$$$)或位置 $$$i + a_i$$$(如果 $$$i + a_i \le n$$$)。
对于从 $$$1$$$ 到 $$$n$$$ 的每个位置 $$$i$$$,您想知道到达任何位置 $$$j$$$ 所需的最小移动次数,这样 $$$a_j$$$ 与 $$$a_i$$$ 具有相反的奇偶性(即,如果 $$$a_i$$$ 是奇数,则 $$$a_j$$$ 必须是偶数,并且反之亦然)。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 中的元素数量。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。
输出
打印 $$$n$$$ 整数 $$$d_1, d_2, \dots, d_n$$$,其中 $$$d_i$$$ 是到达任何位置 $$$j$$$ 所需的最小移动次数,使得 $$$a_j$$$ 与 $$$a_i$$$ 具有相反的奇偶性(即,如果 $$$a_i$$$ 是奇数那么 $$$a_j$$$ 必须是偶数,反之亦然),如果不可能达到这样的位置,则为 -1。
示例
输入 #1
10 4 5 7 6 7 5 4 4 6 4
输出 #1
1 1 1 2 -1 1 1 3 1 1