题目描述

给出一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，当你在第 $i$ 号位置时，你可以一步跳到 $i-a_i$ 或 $i+a_i$。

对于每一个位置 $i$，你想知道最少需要多少步可以到达一个位置 $j$，使得 $a_j$ 与 $a_i$ 的奇偶性不同。

输入格式

第一行一个整数 $n$，表示序列的长度。

第二行 $n$ 个整数 $a_1,a_2, \cdots ,a_n$，表示题目中的序列。

输出格式

一行 $n$ 个整数 $d_1,d_2, \cdots ,d_n$，其中 $d_i$ 表示对于位置 $i$，到达一个位置 $j$，使得 $a_j$ 与 $a_i$ 的奇偶性不同需要的最少步数，如果不能到达这样的位置 $j$，输出$-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$。