Nearest Opposite Parity

题意翻译

## 题目描述 给出一个长度为$n$的序列$a$ 当你在第$i$号位置是，你可以一步调到$i-a_i$和$i+a_i$，前提是$1 \le$ 跳到的位置 $\le n$ 对于每一个位置$i$，你想知道最少需要多少步可以到达一个位置 $j$，使得$a_j$ 与 $a_i$ 的奇偶性不同 ## 输入格式 第一行一个整数$n$，表示序列的长度 第二行$n$个整数$a_1,a_2, \dots ,a_n$，表示题目中的序列 ## 输出格式 一行$n$个整数 $d_1,d_2, \dots ,d_n$，其中$d_i$表示： 对于位置$i$，到达一个位置 $j$，使得$a_j$ 与 $a_i$ 的奇偶性不同需要的最少步数，如果不能到达这样的位置 $j$，输出$-1$ ### 数据范围 $1 \le n \le 2 \cdot 10^5$，$1 \le a_i \le n$ 感谢 @_Wolverine 提供的翻译

题目描述

You are given an array $ a $ consisting of $ n $ integers. In one move, you can jump from the position $ i $ to the position $ i - a_i $ (if $ 1 \le i - a_i $ ) or to the position $ i + a_i $ (if $ i + a_i \le n $ ). For each position $ i $ from $ 1 $ to $ n $ you want to know the minimum the number of moves required to reach any position $ j $ such that $ a_j $ has the opposite parity from $ a_i $ (i.e. if $ a_i $ is odd then $ a_j $ has to be even and vice versa).

输入输出格式

输入格式

The first line of the input contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of elements in $ a $ . The second line of the input contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ ), where $ a_i $ is the $ i $ -th element of $ a $ .

输出格式

Print $ n $ integers $ d_1, d_2, \dots, d_n $ , where $ d_i $ is the minimum the number of moves required to reach any position $ j $ such that $ a_j $ has the opposite parity from $ a_i $ (i.e. if $ a_i $ is odd then $ a_j $ has to be even and vice versa) or -1 if it is impossible to reach such a position.

输入输出样例

输入样例 #1

10
4 5 7 6 7 5 4 4 6 4

输出样例 #1

1 1 1 2 -1 1 1 3 1 1