Nearest Opposite Parity

题目描述

给定一个长度为 $n$ 的下标从 $1$ 开始的数组 $a$，在位置 $i$ 可以移动到位置 $i - a_i(1 \leq i - a_i)$ 或 $i + a_i(i + a_i \leq n)$

现在希望你对于每一个位置 $i$ $(1 \leq i \leq n)$ 求出从这里出发，抵达任意一个位置 $j$ 使得该位置 $j$ 满足 $a_i \bmod 2 \neq a_j \bmod 2$ 的最小步数，如果不存在这样的位置 $j$ 则输出 -1

输入格式

第一行输入一个整数 $n$ $(1 \leq n \leq 2 \times 10^5)$ 为数组长度

第二行输入 $n$ 个整数 $a_i$ $(1 \leq a_i \leq n)$ 为给定的数组

输出格式

输出一行，包含 $n$ 个整数，第 $j$ 个整数为从位置 $j$ 出发的题目所求

样例输入

10
4 5 7 6 7 5 4 4 6 4

样例输出

1 1 1 2 -1 1 1 3 1 1