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).


-----Input-----

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$.


-----Output-----

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.


-----Example-----
Input
10
4 5 7 6 7 5 4 4 6 4

Output
1 1 1 2 -1 1 1 3 1 1

Difficulty: introductory

Starter code:

Solutions:
from heapq import heappush, heappop

n = int(input())
a = list(map(int, input().split()))
edge = [[] for _ in range(n)]
rev = [[] for _ in range(n)]
inf = 10**9
cost = [inf]*n
hq = []

for i, x in enumerate(a):
    if i+x < n:
        edge[i].append(i+x)
        rev[i+x].append(i)
        if (a[i] ^ a[i+x]) & 1:
            cost[i] = 1
    if i-x >= 0:
        edge[i].append(i-x)
        rev[i-x].append(i)
        if (a[i] ^ a[i-x]) & 1:
            cost[i] = 1

    if cost[i] == 1:
        hq.append((1, i))

while hq:
    c, v = heappop(hq)
    if cost[v] < c:
        continue
    c += 1
    for dest in rev[v]:
        if cost[dest] > c:
            cost[dest] = c
            heappush(hq, (c, dest))

for i in range(n):
    if cost[i] == inf:
        cost[i] = -1

print(*cost)


import sys
from itertools import chain, permutations

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split(' ')))


result = [-1 for _ in a]
jumps_to = [[] for _ in a]

for i in range(len(a)):
	left = i - a[i] 
	right = i + a[i]
	if left >= 0:
		jumps_to[left].append(i)
		if (a[left] % 2) != (a[i] % 2):
			result[i] = 1
	if right < n:
		jumps_to[right].append(i)
		if (a[right] % 2) != (a[i] % 2):
			result[i] = 1

queue = []
queue_ptr = 0
for i in range(n):
	if result[i] == 1:
		queue.append(i)

while queue_ptr < len(queue):
	current = queue[queue_ptr]
	for to in jumps_to[current]:
		if result[to] == -1 or result[to] > result[current] + 1:
			queue.append(to)
			result[to] = result[current] + 1
	queue_ptr += 1


#print(jumps_to)

print(" ".join(map(str, result)))

n = int(input())

a = list(map(int, input().split()))

adj = []
for _ in range(n):
    adj.append([])
dist = [-1] * n
q = []

for i, x in enumerate(a):
    for dx in [+x, -x]:
        if 0 <= i + dx < n:
            if a[i+dx]%2==x%2:
                adj[i+dx].append(i)
            else:
                dist[i] = 1
                q.append(i)

q_index = 0
while q_index < len(q):
    top = q[q_index]
    q_index += 1
    
    for nei in adj[top]:
        if dist[nei] == -1:
            dist[nei] = dist[top]+1
            q.append(nei)
            
print(*dist)


from collections import deque
n = int(input())
a = list(map(int,input().split()))
ans = [-1 for _ in range(n)]
graph = [[] for _ in range(n)]

que = deque([])
for i,x in enumerate(a):
    t = False
    if i+x < n:
        if (a[i+x]%2) != (a[i]%2):
            ans[i] = 1
            t = True
        graph[i+x].append(i)
    if i-x >= 0:
        if (a[i-x]%2)!= (a[i]%2):
            ans[i] = 1
            t = True
        graph[i-x].append(i)
    if t:
        que.append(i)
#print(graph)
while len(que) > 0:
    now = que.popleft()
    for ne in graph[now]:
        if ans[ne] == -1:
            ans[ne] = ans[now]+1
            que.append(ne)
        

print(*ans)