E. Ближайшая противоположная четность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. За один ход вы можете прыгнуть с позиции $$$i$$$ в позицию $$$i - a_i$$$ (если $$$1 \le i - a_i$$$) или в позицию $$$i + a_i$$$ (если $$$i + a_i \le n$$$).

Для каждой позиции $$$i$$$ от $$$1$$$ до $$$n$$$ вы хотите узнать минимальное количество ходов, необходимое, чтобы достичь любой позиции $$$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$$$ равно $$$i$$$-му элементу $$$a$$$.

Выходные данные

Выведите $$$n$$$ целых чисел $$$d_1, d_2, \dots, d_n$$$, где $$$d_i$$$ равно минимальному количеству ходов, необходимому, чтобы достичь любой позиции $$$j$$$ такой, что $$$a_j$$$ имеет четность, отличающуюся от четности $$$a_i$$$ (то есть если $$$a_i$$$ нечетно, то $$$a_j$$$ должно быть четным и наоборот) или же -1, если такой позиции достичь невозможно.

Пример
Входные данные
10
4 5 7 6 7 5 4 4 6 4
Выходные данные
1 1 1 2 -1 1 1 3 1 1