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: HARD
Tags: Graph algorithms

Graph traversal

Shortest paths

Starter code:

Solutions:
from copy import deepcopy
from collections import defaultdict
from queue import Queue
n = int(input())
arr = [int(x) for x in input().split()]
d = [-1] * n
parity = [x % 2 for x in arr]
done = Queue()
lrs = defaultdict(list)
for i in range(n):
	put = False
	if i - arr[i] >= 0:
		if parity[i] != parity[i - arr[i]]:
			d[i] = 1
			done.put(i)
			put = True
		lrs[i - arr[i]].append(i)
	if i + arr[i] < n:
		if not put and parity[i] != parity[i + arr[i]]:
			d[i] = 1
			done.put(i)
		lrs[i + arr[i]].append(i)
while not done.empty():
	i = done.get()
	for j in lrs[i]:
		if d[j] == -1:
			d[j] = d[i] + 1
			done.put(j)
print(' '.join([str(x) for x in d]))


from collections import deque

def bfs():
	queue = deque()
	for v in range(n):
		if distance[v] != -1:
			queue.append(v)
	while len(queue) > 0:
		v = queue.popleft()
		for e in edge[v]:
			if distance[e] == -1:
				queue.append(e)
				distance[e] = distance[v] + 1

def main():
	global n, A, distance, edge
	n = int(input())
	A = [int(x) for x in input().strip().split()]
	distance = [-1] * n
	edge = [[] for i in range(n)]
	for i in range(n):
		for m in [i - A[i], i + A[i]]:
			if 0 <= m < n:
				if A[i] & 1 == A[m] & 1:
					edge[m].append(i)
				else:
					distance[i] = 1
	bfs()
	print(*distance)
main()


from collections import defaultdict, deque
import threading
answer = []

def bfs(start, end, g):
	d = [float('inf')] * (len(start) + len(end) + 1)
	q = deque()
	global answer
	for i in start:
		d[i] = 0
		q.append(i)
	while q:
		temp = q.popleft()
		for to in g[temp]:
			if d[to] == float('inf'):
				d[to] = d[temp] + 1
				q.append(to)
	for i in end:
		if d[i] != float('inf'):
			answer[i] = d[i]

def f(a):
	global answer
	n = len(a)
	a = [None] + a
	answer = [-1] * len(a)
	odd = []
	even = []
	g = defaultdict(list)
	for i in range(1, len(a)):
		if a[i] & 1:
			odd.append(i)
		else:
			even.append(i)
		if a[i] + i <= n:
			g[a[i] + i].append(i)
		if i - a[i] >= 1:
			g[i - a[i]].append(i)
	bfs(odd, even, g)
	bfs(even, odd, g)
	return answer[1:]
a = input()
lst = list(map(int, input().strip().split()))
print(*f(lst))


from collections import deque
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
b = list(map(int, input().split()))
adj = [[] for i in range(n + 1)]
odd = []
even = []
for i in range(n):
	p = b[i] + (i + 1)
	if b[i] & 1:
		odd.append(i + 1)
	else:
		even.append(i + 1)
	q = i + 1 - b[i]
	if p <= n:
		adj[p].append(i + 1)
	if q >= 1:
		adj[q].append(i + 1)
ans = [float('inf')] * (n + 1)
val = [float('inf')] * (n + 1)
q = deque()
for j in even:
	val[j] = 0
	q.append(j)
while q:
	u = q.popleft()
	for j in adj[u]:
		if val[j] == float('inf'):
			val[j] = val[u] + 1
			q.append(j)
for j in odd:
	ans[j] = val[j]
val = [float('inf')] * (n + 1)
q = deque()
for j in odd:
	val[j] = 0
	q.append(j)
while q:
	u = q.popleft()
	for j in adj[u]:
		if val[j] == float('inf'):
			val[j] = val[u] + 1
			q.append(j)
for j in even:
	ans[j] = val[j]
res = []
for j in range(1, n + 1):
	if ans[j] == float('inf'):
		res.append(-1)
	else:
		res.append(ans[j])
print(*res)


import sys
from collections import deque

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
N = INT()
A = LIST()
que = deque()
nodes = [[] for i in range(N)]
for (i, a) in enumerate(A):
	if i + a < N:
		nodes[i + a].append(i)
		if a % 2 != A[i + a] % 2:
			que.append((i, 1))
			continue
	if i - a >= 0:
		nodes[i - a].append(i)
		if a % 2 != A[i - a] % 2:
			que.append((i, 1))
ans = [-1] * N
while que:
	(u, cost) = que.popleft()
	if ans[u] != -1:
		continue
	ans[u] = cost
	for v in nodes[u]:
		que.append((v, cost + 1))
print(*ans)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
INF = float('inf')
mod = int(1000000000.0) + 7

def dijkstra(n, graph):
	dist = [-1] * n
	vis = [0] * n
	queue = deque()
	for i in range(n):
		if i + a[i] < n and (a[i] + a[i + a[i]]) % 2 != 0 or (i - a[i] >= 0 and (a[i] + a[i - a[i]]) % 2 != 0):
			dist[i] = 1
			queue.append(i)
			vis[i] = 1
	while queue:
		v = queue.popleft()
		for u in graph[v]:
			if vis[u] == 0:
				dist[u] = 1 + dist[v]
				queue.append(u)
				vis[u] = 1
	return dist
n = int(data())
a = mdata()
graph = [[] for i in range(n)]
for i in range(n):
	if i + a[i] < n:
		graph[i + a[i]].append(i)
	if i - a[i] >= 0:
		graph[i - a[i]].append(i)
dist = dijkstra(n, graph)
outl(dist)


from collections import deque
import sys
input = sys.stdin.readline

def bfs0(s):
	q = deque()
	dist = [inf] * n
	for i in s:
		q.append(i)
		dist[i] = 0
	while q:
		i = q.popleft()
		di = dist[i]
		for j in G[i]:
			if dist[j] > di + 1:
				q.append(j)
				dist[j] = di + 1
	return dist

def bfs1(s):
	q = deque()
	dist = [inf] * n
	for i in s:
		q.append(i)
		dist[i] = 0
	while q:
		i = q.popleft()
		di = dist[i]
		for j in H[i]:
			if dist[j] > di + 1:
				q.append(j)
				dist[j] = di + 1
	return dist
n = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(n)]
H = [[] for _ in range(n)]
(s0, s1) = (set(), set())
for i in range(n):
	ai = a[i]
	if ai % 2 == 0:
		if i + ai < n:
			G[i + ai].append(i)
			if a[i + ai] % 2 == 1:
				s0.add(i + ai)
		if 0 <= i - ai:
			G[i - ai].append(i)
			if a[i - ai] % 2 == 1:
				s0.add(i - ai)
	else:
		if i + ai < n:
			H[i + ai].append(i)
			if a[i + ai] % 2 == 0:
				s1.add(i + ai)
		if 0 <= i - ai:
			H[i - ai].append(i)
			if a[i - ai] % 2 == 0:
				s1.add(i - ai)
inf = 1145141919
dist0 = bfs0(s0)
dist1 = bfs1(s1)
ans = []
for i in range(n):
	m = inf
	if 0 < dist0[i]:
		m = min(m, dist0[i] + 1)
	if 0 < dist1[i]:
		m = min(m, dist1[i] + 1)
	m %= inf
	m -= 1
	ans.append(m)
print(*ans)


import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
E = [[] for i in range(n + 1)]
from collections import deque
ODD = deque()
EVEN = deque()
for i in range(n):
	if i + 1 + A[i] < n + 1:
		E[i + 1 + A[i]].append(i + 1)
	if i + 1 - A[i] >= 0:
		E[i + 1 - A[i]].append(i + 1)
	if A[i] % 2 == 1:
		ODD.append(i + 1)
	else:
		EVEN.append(i + 1)
AODD = [-1] * (n + 1)
AEVEN = [-1] * (n + 1)
count = 1
while ODD:
	NODD = deque()
	while ODD:
		x = ODD.pop()
		for to in E[x]:
			if AODD[to] == -1:
				AODD[to] = count
				NODD.append(to)
	ODD = NODD
	count += 1
count = 1
while EVEN:
	NEVEN = deque()
	while EVEN:
		x = EVEN.pop()
		for to in E[x]:
			if AEVEN[to] == -1:
				AEVEN[to] = count
				NEVEN.append(to)
	EVEN = NEVEN
	count += 1
for i in range(n):
	if A[i] % 2 == 1:
		print(AEVEN[i + 1], end=' ')
	else:
		print(AODD[i + 1], end=' ')


def bfs(a, f, g):
	v = [0 if i % 2 == f else -1 for i in a]
	s = [(i, 0) for (i, v) in enumerate(a) if v % 2 == f]
	while len(s):
		ns = []
		for (ci, c) in s:
			for i in g[ci]:
				if v[i] > c + 1 or v[i] == -1:
					v[i] = c + 1
					ns.append((i, c + 1))
		s = ns
	return v

def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	g = list(map(set, [[]] * n))
	for (i, v) in enumerate(a):
		if i - v >= 0:
			g[i - v].add(i)
		if i + v < len(a):
			g[i + v].add(i)
	g = list(map(list, g))
	(o, e) = (bfs(a, 0, g), bfs(a, 1, g))
	print(*map(sum, zip(o, e)))
solve()


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


from sys import stdin, stdout
from collections import deque
n = int(stdin.readline().strip())
alist = list(map(int, stdin.readline().split()))
nop = {}
p = [set() for _ in range(n)]

def back(next):
	while next:
		(i, c) = next.popleft()
		if c < nop[i]:
			nop[i] = c
			c += 1
			for j in p[i]:
				next.append((j, c))

def bfs(x):
	if x not in nop:
		next = deque([x])
		pr = alist[x] % 2
		nop[x] = n
		while next:
			i = next.popleft()
			for j in [i - alist[i], i + alist[i]]:
				if j >= 0 and j < n:
					p[j].add(i)
					if alist[j] % 2 != pr:
						back(deque([(i, 1)]))
					elif j in nop:
						back(deque([(i, nop[j] + 1)]))
					else:
						nop[j] = n
						next.append(j)
	return nop[x] if nop[x] < n else -1
stdout.write(' '.join((str(bfs(x)) for x in range(n))))


n = int(input())
a = list(map(int, input().split()))
e = [[] for i in range(n)]
for i in range(n):
	v = a[i]
	if i - v >= 0:
		e[i - v].append(i)
	if i + v < n:
		e[i + v].append(i)
q = [0] * n
res = [-1] * n
for rem in range(2):
	d = [None] * n
	ql = 0
	qr = 0
	for i in range(n):
		if a[i] % 2 == rem:
			q[qr] = i
			qr += 1
			d[i] = 0
	while ql < qr:
		x = q[ql]
		ql += 1
		dd = d[x] + 1
		for v in e[x]:
			if d[v] is None:
				d[v] = dd
				res[v] = dd
				q[qr] = v
				qr += 1
print(*res)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
n = inp()
a = inpl()
res = [-1] * n
q = deque([])
g = [[] for _ in range(n)]
for (i, x) in enumerate(a):
	ok = 0
	if i - x >= 0:
		g[i - x].append(i)
		if x % 2 != a[i - x] % 2:
			ok = 1
	if i + x < n:
		g[i + x].append(i)
		if x % 2 != a[i + x] % 2:
			ok = 1
	if ok:
		q.append(i)
		res[i] = 1
while q:
	v = q.popleft()
	for u in g[v]:
		if res[u] == -1:
			res[u] = res[v] + 1
			q.append(u)
print(*res)


from collections import deque

def main():
	n = int(input())
	a = readIntArr()
	backwards = [[] for _ in range(n)]
	ans = [inf for _ in range(n)]
	q = deque()
	for i in range(n):
		x = i - a[i]
		if x >= 0:
			if a[i] % 2 == a[x] % 2:
				backwards[x].append(i)
			else:
				ans[i] = 1
				q.append([i, 1])
		y = i + a[i]
		if y < n:
			if a[i] % 2 == a[y] % 2:
				backwards[y].append(i)
			else:
				ans[i] = 1
				q.append([i, 1])
	while q:
		(node, d) = q.popleft()
		for nex in backwards[node]:
			if ans[nex] == inf:
				ans[nex] = d + 1
				q.append([nex, d + 1])
	for i in range(n):
		if ans[i] == inf:
			ans[i] = -1
	oneLineArrayPrint(ans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
input = sys.stdin.readline
from collections import *

def bfs(s):
	q = deque([])
	dist = [-1] * n
	for i in range(n):
		if a[i] % 2 == s:
			q.append(i)
			dist[i] = 0
	while q:
		v = q.popleft()
		for nv in G[v]:
			if dist[nv] == -1:
				dist[nv] = dist[v] + 1
				q.append(nv)
	return dist
n = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(n)]
for i in range(n):
	s = i
	t1 = i - a[i]
	t2 = i + a[i]
	if t1 >= 0:
		G[t1].append(s)
	if t2 < n:
		G[t2].append(s)
to_even = bfs(0)
to_odd = bfs(1)
ans = []
for i in range(n):
	if a[i] % 2 == 0:
		ans.append(to_odd[i])
	else:
		ans.append(to_even[i])
print(*ans)


from math import inf
n = int(input())
l = [-1]
l.extend(list(map(int, input().split())))
g = [[] for _ in range(n + 1)]
for i in range(1, n + 1):
	if i + l[i] <= n:
		g[i + l[i]].append(i)
	if i - l[i] > 0:
		g[i - l[i]].append(i)
ans = [-1] * n

def bfs(v):
	vis = [0] * (n + 1)
	q = []
	for i in range(1, n + 1):
		if l[i] % 2 == v:
			q.append((i, 0))
	pos = 0
	while len(q) > pos:
		(i, dis) = q[pos]
		pos += 1
		if vis[i] == 1:
			continue
		vis[i] = 1
		if not l[i] % 2 == v:
			ans[i - 1] = dis
		for j in g[i]:
			q.append((j, dis + 1))
bfs(0)
bfs(1)
print(*ans)


n = int(input())
a = list(map(int, input().strip().split()))
r = [-1] * n
e = [[] for i in range(n)]
for (i, v) in enumerate(a):
	if i - v >= 0:
		e[i - v].append(i)
	if i + v < n:
		e[i + v].append(i)
from collections import deque
b1 = deque()
t = [-1] * n
for (i, v) in enumerate(a):
	if v & 1:
		b1.append(i)
		t[i] = 0
while b1:
	p = b1.popleft()
	for i in e[p]:
		if t[i] < 0:
			t[i] = t[p] + 1
			b1.append(i)
for (i, v) in enumerate(a):
	if not v & 1:
		r[i] = t[i]
b2 = deque()
t = [-1] * n
for (i, v) in enumerate(a):
	if not v & 1:
		b2.append(i)
		t[i] = 0
while b2:
	p = b2.popleft()
	for i in e[p]:
		if t[i] < 0:
			t[i] = t[p] + 1
			b2.append(i)
for (i, v) in enumerate(a):
	if v & 1:
		r[i] = t[i]
print(*r)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)
from math import inf
from collections import deque

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [-1] * n
	oof = [[] for __ in range(n)]
	oof2 = [[] for __ in range(n)]
	(q1, q2) = (deque(), deque())
	for i in range(n):
		if a[i] % 2:
			q2.append(i)
			if i + a[i] < n:
				oof2[i + a[i]] += [i]
			if i - a[i] >= 0:
				oof2[i - a[i]] += [i]
		else:
			q1.append(i)
			if i + a[i] < n:
				oof[i + a[i]] += [i]
			if i - a[i] >= 0:
				oof[i - a[i]] += [i]
	(ans1, ans2) = ([0] * n, [0] * n)
	while q1:
		next = q1.popleft()
		for each in oof2[next]:
			if not ans1[each]:
				ans1[each] = ans1[next] + 1
				q1.append(each)
	while q2:
		next = q2.popleft()
		for each in oof[next]:
			if not ans2[each]:
				ans2[each] = ans2[next] + 1
				q2.append(each)
	for i in range(n):
		if a[i] % 2 and ans1[i] or (not a[i] % 2 and ans2[i]):
			ans[i] = max(ans1[i], ans2[i])
	print(*ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	n = N()
	arr = RLL()
	gp = [[] for _ in range(n + 1)]
	evq = deque()
	odq = deque()
	rece = [INF] * (n + 1)
	reco = [INF] * (n + 1)
	for i in range(n):
		now = i + 1
		(pre, suf) = (now - arr[i], now + arr[i])
		if pre >= 1:
			gp[pre].append(now)
		if suf <= n:
			gp[suf].append(now)
		if arr[i] % 2 == 0:
			evq.append(now)
			rece[now] = 0
		else:
			odq.append(now)
			reco[now] = 0
	while evq:
		now = evq.popleft()
		for nex in gp[now]:
			if rece[nex] > rece[now] + 1:
				evq.append(nex)
				rece[nex] = rece[now] + 1
	while odq:
		now = odq.popleft()
		for nex in gp[now]:
			if reco[nex] > reco[now] + 1:
				odq.append(nex)
				reco[nex] = reco[now] + 1
	res = []
	for i in range(n):
		if arr[i] % 2 == 0:
			res.append(reco[i + 1] if reco[i + 1] != INF else -1)
		else:
			res.append(rece[i + 1] if rece[i + 1] != INF else -1)
	print(*res)
main()


from collections import deque
n = int(input())
inf = 10 ** 9
a = list(map(int, input().split()))
g = [set() for i in range(n)]
(q, qq) = (deque(), deque())
ans = [inf] * n
anss = [inf] * n
used = [True] * n
usedd = [True] * n
for i in range(n):
	if a[i] % 2 == 0:
		q.append(i)
		used[i] = False
		ans[i] = 0
	else:
		qq.append(i)
		anss[i] = 0
		usedd[i] = False
	if i - a[i] >= 0:
		g[i - a[i]].add(i)
	if i + a[i] < n:
		g[i + a[i]].add(i)
while len(q) > 0:
	x = q.popleft()
	for i in g[x]:
		if used[i]:
			ans[i] = ans[x] + 1
			q.append(i)
			used[i] = False
while len(qq) > 0:
	x = qq.popleft()
	for i in g[x]:
		if usedd[i]:
			anss[i] = anss[x] + 1
			qq.append(i)
			usedd[i] = False
write = [0] * n
for i in range(n):
	if a[i] % 2 == 0:
		write[i] = anss[i]
	else:
		write[i] = ans[i]
	if write[i] == inf:
		write[i] = -1
print(*write)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default='z', func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
n = int(input())
l = list(map(int, input().split()))
d = defaultdict(list)
ans = [-1] * n
s = set()
for i in range(n):
	if 0 <= i + l[i] <= n - 1:
		if l[i] % 2 != l[i + l[i]] % 2:
			ans[i] = 1
			s.add(i)
		else:
			d[i + l[i]].append(i)
	if 0 <= i - l[i] <= n - 1:
		if l[i] % 2 != l[i - l[i]] % 2:
			ans[i] = 1
			s.add(i)
		else:
			d[i - l[i]].append(i)
while len(s) > 0:
	s1 = set()
	for i in s:
		for j in d[i]:
			if ans[j] != -1:
				continue
			ans[j] = ans[i] + 1
			s1.add(j)
	s = s1
print(*ans)


from collections import deque, defaultdict

def bfs():
	queue = deque()
	dist = [-1] * n
	adj = defaultdict(list)
	for i in range(n):
		if i - arr[i] >= 0:
			adj[i - arr[i]].append(i)
			if arr[i] % 2 != arr[i - arr[i]] % 2:
				dist[i] = 1
		if i + arr[i] < n:
			adj[i + arr[i]].append(i)
			if arr[i] % 2 != arr[i + arr[i]] % 2:
				dist[i] = 1
		if dist[i] == 1:
			queue.append(i)
	while queue:
		index = queue.popleft()
		for negh in adj[index]:
			if dist[negh] == -1 and arr[negh] % 2 == arr[index] % 2:
				dist[negh] = dist[index] + 1
				queue.append(negh)
	return dist
n = int(input())
arr = list(map(int, input().split()))
ans = bfs()
for ch in ans:
	print(ch, end=' ')
print()


import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 18
ans = [INF] * n

def bfs(starts, ends):
	global ans
	d = [INF] * n
	dq = deque([])
	for x in starts:
		d[x] = 0
		dq.append(x)
	while dq:
		ver = dq.popleft()
		for to in inv_g[ver]:
			if d[to] == INF:
				d[to] = d[ver] + 1
				dq.append(to)
	for i in ends:
		if d[i] != INF:
			ans[i] = d[i]
inv_g = [[] for i in range(n)]
for i in range(n):
	if i - a[i] >= 0:
		inv_g[i - a[i]].append(i)
	if i + a[i] < n:
		inv_g[i + a[i]].append(i)
odd = []
even = []
for i in range(n):
	if a[i] % 2:
		odd.append(i)
	else:
		even.append(i)
bfs(odd, even)
bfs(even, odd)
for i in range(n):
	if ans[i] == INF:
		ans[i] = -1
print(*ans)


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

def valid(x, n):
	if x >= 0 and x < n:
		return True
	return False

def push(u, v, g):
	if u not in g:
		g[u] = set()
	g[u].add(v)
rg = {}
s_set = set()
for (i, x) in enumerate(a):
	if valid(i + x, n) == True:
		push(i + x, i, rg)
		if (a[i] + a[i + x]) % 2 == 1:
			s_set.add(i)
	if valid(i - x, n) == True:
		push(i - x, i, rg)
		if (a[i] + a[i - x]) % 2 == 1:
			s_set.add(i)
Q = []
used = [-1 for _ in range(n)]
for x in s_set:
	used[x] = 1
	Q.append([x, 1])
i = 0
while i < len(Q):
	(u, dis) = Q[i]
	if u in rg:
		for v in rg[u]:
			if used[v] == -1:
				used[v] = dis + 1
				Q.append([v, dis + 1])
	i += 1
print(' '.join([str(x) for x in used]))


from collections import deque
n = int(input())
A = [0] + [int(x) for x in input().strip().split()]
D = [-1] * (n + 1)
N = [[] for i in range(n + 1)]
Q = deque()
for p in range(1, n + 1):
	parity = A[p] % 2
	left = p - A[p]
	right = p + A[p]
	if left > 0:
		if parity == A[left] % 2:
			N[left].append(p)
		else:
			D[p] = 1
			Q.append(p)
	if right <= n:
		if parity == A[right] % 2:
			N[right].append(p)
		else:
			D[p] = 1
			Q.append(p)
while len(Q) > 0:
	q = Q.popleft()
	for n in N[q]:
		if D[n] == -1:
			Q.append(n)
			D[n] = D[q] + 1
print(*D[1:])


from sys import stdin, stdout
from collections import deque
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
(pares, impares) = ([], [])
ady = [[] for i in range(n)]
sol = ['-1' for i in range(n)]
for i in range(n):
	ai = a[i]
	izq = i - ai
	der = i + ai
	if izq >= 0:
		ady[izq].append(i)
	if der < n:
		ady[der].append(i)
	if ai % 2 == 0:
		pares.append(i)
	else:
		impares.append(i)

def BFS(red, blue):
	d = [-1 for i in range(n)]
	q = deque()
	for u in red:
		d[u] = 0
		q.append(u)
	while len(q) > 0:
		v = q.popleft()
		for i in ady[v]:
			if d[i] == -1:
				d[i] = d[v] + 1
				q.append(i)
	for i in blue:
		if d[i] != -1:
			sol[i] = str(d[i])
BFS(pares, impares)
BFS(impares, pares)
stdout.write(' '.join(sol))


INF = 10 ** 10

def main():
	print = out.append
	n = get_int()
	li = get_list()
	adj = [[] for _ in range(n)]
	for (i, ele) in enumerate(li):
		if i - ele >= 0:
			adj[i - ele].append(i)
		if i + ele < n:
			adj[i + ele].append(i)
	(cost_odd, cost_even) = ([-1] * n, [-1] * n)
	queue = [i for (i, ele) in enumerate(li) if ele % 2 == 0]
	for i in queue:
		cost_odd[i] = 0
	curr_cost = 1
	while len(queue) > 0:
		new_q = []
		for vertex in queue:
			for i in adj[vertex]:
				if cost_odd[i] == -1:
					new_q.append(i)
					cost_odd[i] = curr_cost
		queue = new_q
		curr_cost += 1
	queue = [i for (i, ele) in enumerate(li) if ele % 2 != 0]
	for i in queue:
		cost_even[i] = 0
	curr_cost = 1
	while len(queue) > 0:
		new_q = []
		for vertex in queue:
			for i in adj[vertex]:
				if cost_even[i] == -1:
					new_q.append(i)
					cost_even[i] = curr_cost
		queue = new_q
		curr_cost += 1
	res = []
	for (i, ele) in enumerate(li):
		if ele % 2 == 0:
			res.append(cost_even[i])
		else:
			res.append(cost_odd[i])
	print(' '.join(map(str, res)))
import sys
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
main()
print(*out, sep='\n')


input()
n = map(int, input().split())
n = list(n)
ans = len(n) * [-1]
a = []
go = [[] for _ in range(len(n))]
for (i, x) in enumerate(n):
	for y in (x, -x):
		y += i
		if y >= 0 and y < len(n):
			if x % 2 != n[y] % 2:
				ans[i] = 1
				a.append(i)
			else:
				go[y].append(i)
while len(a) != 0:
	b = []
	for x in a:
		for y in go[x]:
			if ans[y] == -1:
				ans[y] = ans[x] + 1
				b.append(y)
	a = b
for (i, x) in enumerate(ans):
	ans[i] = str(x)
print(' '.join(ans))


import sys
from collections import deque
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
n = int(input())
a = list(map(int, input().split()))
ans = [-1] * n
ends = {0: set(), 1: set()}
for (i, el) in enumerate(a):
	if i - el >= 0 and a[i - el] + el & 1:
		ends[el & 1].add(i)
	elif i + el < n and a[i + el] + el & 1:
		ends[el & 1].add(i)
g = [[] for _ in range(n)]
for (i, el) in enumerate(a):
	if i - el >= 0 and (not a[i - el] + el & 1):
		g[i - el].append(i)
	if i + el < n and (not a[i + el] + el & 1):
		g[i + el].append(i)
visited = [False] * n
for i in range(2):
	queue = deque(((v, 1) for v in ends[i]))
	while queue:
		(v, d) = queue.popleft()
		if not visited[v]:
			visited[v] = True
			ans[v] = d
			for to in g[v]:
				queue.append((to, d + 1))
print(*ans)


from collections import deque
n = int(input())
a = [int(s) for s in input().split(' ')]
adj = [[] for _ in range(n)]
for i in range(n):
	j = i - a[i]
	if j >= 0:
		adj[j].append(i)
	j = i + a[i]
	if j < n:
		adj[j].append(i)
ans = [-1] * n
for parity in range(2):
	q = deque()
	dist = [-1] * n
	for i in range(n):
		if a[i] % 2 == parity:
			q.append(i)
			dist[i] = 0
	while q:
		u = q.popleft()
		for v in adj[u]:
			if dist[v] == -1:
				dist[v] = dist[u] + 1
				q.append(v)
	for i in range(n):
		if a[i] % 2 != parity and dist[i] != -1:
			ans[i] = dist[i]
print(' '.join((str(x) for x in ans)))


from collections import deque
n = int(input())
a = [int(x) for x in input().split()]
d = [-1] * n
line = [[] for i in range(n)]
for i in range(n):
	for j in [i - a[i], i + a[i]]:
		if 0 <= j < n:
			if a[i] % 2 == a[j] % 2:
				line[j].append(i)
			else:
				d[i] = 1
q = deque()
for i in range(n):
	if d[i] == 1:
		q.append(i)
while q:
	t = q.popleft()
	for i in line[t]:
		if d[i] == -1:
			d[i] = d[t] + 1
			q.append(i)
print(*d)


import sys
input = sys.stdin.readline
from collections import deque
N = 2 * 10 ** 5 + 5
g = [[] for _ in range(N)]
n = int(input())
a = list(map(int, input().split()))
dist = [10 ** 9] * N
for i in range(n):
	if i - a[i] >= 0:
		g[i - a[i]].append(i)
		if a[i - a[i]] % 2 != a[i] % 2:
			dist[i] = 1
	if i + a[i] < n:
		g[i + a[i]].append(i)
		if a[i + a[i]] % 2 != a[i] % 2:
			dist[i] = 1
q = deque([])
for i in range(n):
	if dist[i] == 1:
		q.append(i)
while len(q):
	cur = q[0]
	q.popleft()
	for nxt in g[cur]:
		if dist[nxt] > dist[cur] + 1:
			dist[nxt] = dist[cur] + 1
			q.append(nxt)
print(*[dist[i] if dist[i] < 1000000000.0 else -1 for i in range(n)])


n = int(input())
a = [0] + [int(x) for x in input().split()]
vis = set()
q = []
ans = [-1 for i in range(n + 5)]
to = [[] for i in range(n + 5)]
for i in range(1, n + 1):
	if i - a[i] >= 1:
		if a[i - a[i]] % 2 == a[i] % 2:
			to[i - a[i]].append(i)
		else:
			q.append(i)
			ans[i] = 1
			vis.add(i)
	if i + a[i] <= n:
		if a[i + a[i]] % 2 == a[i] % 2:
			to[i + a[i]].append(i)
		elif i not in vis:
			q.append(i)
			ans[i] = 1
			vis.add(i)
head = 0
while head < len(q):
	pos = q[head]
	head += 1
	for t in to[pos]:
		if t not in vis:
			ans[t] = ans[pos] + 1
			vis.add(t)
			q.append(t)
print(*ans[1:n + 1])


n = int(input())
parities = list(map(int, input().strip().split()))
first_layer = []
ans = [-1 for i in range(n)]
hopTo = [[] for i in range(n)]
for i in range(n):
	appended = False
	if i - parities[i] >= 0:
		hopTo[i - parities[i]].append(i)
		if (parities[i] + parities[i - parities[i]]) % 2:
			first_layer.append(i)
			appended = True
	if i + parities[i] <= n - 1:
		hopTo[i + parities[i]].append(i)
		if (parities[i] + parities[i + parities[i]]) % 2 and appended == False:
			first_layer.append(i)
calculated = 0
for i in first_layer:
	ans[i] = 1
	calculated += 1

def next_layer(cur_layer, calced, layer_num):
	new_layer = []
	for point in cur_layer:
		for next_point in hopTo[point]:
			if ans[next_point] == -1:
				ans[next_point] = layer_num + 1
				new_layer.append(next_point)
				calced += 1
	return [new_layer, calced, layer_num + 1]
cur_layer = first_layer
layer_num = 1
while 1:
	data = next_layer(cur_layer, calculated, layer_num)
	cur_layer = data[0]
	calculated = data[1]
	layer_num = data[2]
	if len(cur_layer) == 0:
		for i in ans:
			print(i, end=' ')
		break


from sys import stdin, stdout
get_string = lambda : stdin.readline().strip()
get_intmap = lambda : map(int, get_string().split())

def testcase():
	n = int(input())
	adj = [[] for i in range(n + 1)]
	(odd_vertices, even_vertices) = ([], [])
	for (ind, ai) in zip(range(1, n + 1), get_intmap()):
		(ind1, ind2) = (ind - ai, ind + ai)
		if ind1 >= 1:
			adj[ind1].append(ind)
		if ind2 <= n:
			adj[ind2].append(ind)
		if ai % 2 == 1:
			odd_vertices.append(ind)
		else:
			even_vertices.append(ind)
	distance = [-1] * (n + 1)
	for frontier in (even_vertices, odd_vertices):
		used = [0] * (n + 1)
		for v in frontier:
			used[v] = 1
		curr_distance = 0
		nxt = []
		while len(frontier):
			curr_distance += 1
			for u in frontier:
				for v in adj[u]:
					if not used[v]:
						used[v] = 1
						distance[v] = curr_distance
						nxt.append(v)
			frontier = nxt
			nxt = []
	print(' '.join([str(i) for i in distance[1:]]))
testcase()
quit()
for t in range(int(input())):
	testcase()


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
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
graph = [[] for _ in range(N)]
q1 = []
q2 = []
for (i, a) in enumerate(A):
	if i - a >= 0:
		graph[i - a].append(i)
	if i + a <= N - 1:
		graph[i + a].append(i)
	if a % 2 == 1:
		q1.append(i)
	else:
		q2.append(i)
D = [-1] * N
d = 0
while q1:
	qq = []
	d += 1
	for p in q1:
		for np in graph[p]:
			if D[np] == -1 and A[np] % 2 == 0:
				D[np] = d
				qq.append(np)
	q1 = qq
d = 0
while q2:
	qq = []
	d += 1
	for p in q2:
		for np in graph[p]:
			if D[np] == -1 and A[np] % 2 == 1:
				D[np] = d
				qq.append(np)
	q2 = qq
print(*D)


n = int(input())
arr = list(map(int, input().split()))
adj = {}
ans = [-1] * n
queue = []
for i in range(n):
	flg = True
	if i + arr[i] < n:
		if arr[i + arr[i]] % 2 == arr[i] % 2:
			try:
				adj[i + arr[i]].append(i)
			except:
				adj[i + arr[i]] = [i]
		else:
			ans[i] = 1
			flg = False
			queue.append(i)
	if i - arr[i] >= 0:
		if arr[i - arr[i]] % 2 == arr[i] % 2:
			try:
				adj[i - arr[i]].append(i)
			except:
				adj[i - arr[i]] = [i]
		elif flg:
			ans[i] = 1
			queue.append(i)
q_index = 0
while q_index < len(queue):
	z = queue[q_index]
	q_index += 1
	for i in adj.get(z, []):
		if ans[i] == -1:
			ans[i] = ans[z] + 1
			queue.append(i)
print(*ans)


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
inf = float('inf')
from functools import cmp_to_key
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def solve():
	n = geta()
	a = getl()
	cost = [inf] * n
	vis = [False] * n
	edges = dd(list)
	odd = []
	even = []
	for i in range(n):
		if a[i] & 1:
			odd.append(i)
		else:
			even.append(i)
		next = i - a[i]
		prev = i + a[i]
		for index in [next, prev]:
			if 0 <= index < n:
				edges[index].append(i)

	def bfs(let):
		q = deque()
		vis = [False] * n
		for i in let:
			q.append((i, 0))
			vis[i] = True
		while q:
			(now, dist) = q.popleft()
			for node in edges[now]:
				cost[node] = min(cost[node], dist + 1)
				if not vis[node]:
					vis[node] = True
					q.append((node, dist + 1))
	ans = [-1] * n
	bfs(odd)
	for i in range(n):
		if a[i] & 1 == 0:
			ans[i] = cost[i]
	cost = [inf] * n
	bfs(even)
	for i in range(n):
		if a[i] & 1:
			ans[i] = cost[i]
	ans = [i if i != inf else -1 for i in ans]
	print(*ans)
solve()


n = int(input())
a = list(map(int, input().split()))
parity = lambda x: x & 1
q = []
ans = [-1] * n
graph = [[] for i in range(n)]
for i in range(n):
	if i - a[i] >= 0:
		if parity(a[i]) ^ parity(a[i - a[i]]):
			ans[i] = 1
			q.append(i)
		else:
			graph[i - a[i]].append(i)
	if i + a[i] < n:
		if parity(a[i]) ^ parity(a[i + a[i]]):
			ans[i] = 1
			q.append(i)
		else:
			graph[i + a[i]].append(i)
i = 0
while i < len(q):
	u = q[i]
	i += 1
	for v in graph[u]:
		if ans[v] == -1:
			q.append(v)
			ans[v] = ans[u] + 1
print(' '.join([str(i) for i in ans]) + '\n')


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
UNDEF = -1
n = int(input())
a = list(map(int, input().split()))
g = [[] for _ in range(n)]
for (v, step) in enumerate(a):
	if v + step < n:
		g[v + step].append(v)
	if v - step >= 0:
		g[v - step].append(v)
ret = [UNDEF] * n
for parity in range(0, 2):
	dist = [UNDEF] * n
	q = deque()
	for v in range(n):
		if a[v] & 1 == parity:
			dist[v] = 0
			q.append(v)
	while q:
		cur = q.popleft()
		for to in g[cur]:
			if dist[to] == UNDEF:
				dist[to] = dist[cur] + 1
				q.append(to)
	for v in range(n):
		if a[v] & 1 != parity:
			ret[v] = dist[v]
print(*ret)


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(' '.join(map(str, result)))


import sys
import math
from collections import defaultdict, Counter, deque
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for i in range(1):
	n = int(input())
	a = list(map(int, input().split()))
	l = defaultdict(list)
	q = deque()
	for j in range(n):
		if j + a[j] < n:
			l[j + a[j]].append(j)
			if a[j] & 1 ^ a[j + a[j]] & 1:
				q.append(j)
		if j - a[j] >= 0:
			l[j - a[j]].append(j)
			if a[j] & 1 ^ a[j - a[j]] & 1:
				q.append(j)
	ans = [-1] * n
	lev = [-1] * n
	for j in q:
		lev[j] = 1
	while q:
		s = q.popleft()
		ans[s] = lev[s]
		for j in l[s]:
			if lev[j] == -1:
				q.append(j)
				lev[j] = lev[s] + 1
	print(*ans)


from sys import stdin, stdout
from collections import deque
import bisect
R = lambda : stdin.readline().strip()
RL = lambda f=None: list(map(f, R().split(' '))) if f else list(R().split(' '))
output = lambda x: stdout.write(str(x) + '\n')
output_list = lambda x: output(' '.join(map(str, x)))

def makeG(l):
	graph = [[] for i in range(n + 1)]
	for i in range(len(l)):
		if i + 1 - l[i] >= 1:
			graph[i + 1 - l[i]].append(i + 1)
		if i + 1 + l[i] <= n:
			graph[i + 1 + l[i]].append(i + 1)
	return graph

def multibfs(q, eo):
	ind = 0
	while ind < len(q):
		for j in g[q[ind]]:
			if ans[j - 1] == -1 and l[j - 1] % 2 == eo:
				ans[j - 1] = ans[q[ind] - 1] + 1
				q.append(j)
		ind += 1
n = int(R())
l = RL(int)
ev = []
od = []
for i in range(n):
	if l[i] % 2:
		od.append(i + 1)
	else:
		ev.append(i + 1)
g = makeG(l)
ans = [-1] * n
st = []
for i in ev:
	for j in g[i]:
		if l[j - 1] % 2:
			ans[j - 1] = 1
			st.append(j)
multibfs(st, 1)
st = []
for i in od:
	for j in g[i]:
		if l[j - 1] % 2 == 0:
			ans[j - 1] = 1
			st.append(j)
multibfs(st, 0)
output_list(ans)


n = int(input())
v = list(map(int, input().split()))
g = []
for i in range(0, n):
	g.append([])
ans = [-1] * n
for i in range(0, n):
	pz = i - v[i]
	if pz >= 0:
		g[pz].append(i)
		if v[i] % 2 != v[pz] % 2:
			ans[i] = 1
	pz = i + v[i]
	if pz < n:
		g[pz].append(i)
		if v[i] % 2 != v[pz] % 2:
			ans[i] = 1
q = []
for i in range(n):
	if ans[i] == 1:
		q.append(i)
pz = 0
while pz < len(q):
	nod = q[pz]
	for vec in g[nod]:
		if ans[vec] == -1:
			ans[vec] = ans[nod] + 1
			q.append(vec)
	pz += 1
print(*ans)


from collections import deque
n = int(input())
a = list(map(int, input().split()))
to = [[] for i in range(n + 3)]
for i in range(n):
	if i + 1 + a[i] <= n:
		to[i + 1 + a[i]].append(i + 1)
	if i + 1 - a[i] > 0:
		to[i + 1 - a[i]].append(i + 1)
for i in range(1, n + 1):
	if a[i - 1] % 2 == 0:
		to[n + 2].append(i)
	else:
		to[n + 1].append(i)
evendist = [10 ** 15] * (n + 3)
evendist[n + 1] = 0
que = deque([n + 1])
while que:
	v = que.popleft()
	if v == n + 1:
		for nv in to[v]:
			if evendist[nv] > evendist[v]:
				evendist[nv] = evendist[v]
				que.appendleft(nv)
	else:
		for nv in to[v]:
			if evendist[nv] > evendist[v] + 1:
				evendist[nv] = evendist[v] + 1
				que.append(nv)
odddist = [10 ** 15] * (n + 3)
odddist[n + 2] = 0
que = deque([n + 2])
while que:
	v = que.popleft()
	if v == n + 2:
		for nv in to[v]:
			if odddist[nv] > odddist[v]:
				odddist[nv] = odddist[v]
				que.appendleft(nv)
	else:
		for nv in to[v]:
			if odddist[nv] > odddist[v] + 1:
				odddist[nv] = odddist[v] + 1
				que.append(nv)
ans = [0] * n
for i in range(n):
	if a[i] % 2 == 0:
		ans[i] = evendist[i + 1]
		if ans[i] == 10 ** 15:
			ans[i] = -1
	else:
		ans[i] = odddist[i + 1]
		if ans[i] == 10 ** 15:
			ans[i] = -1
print(*ans)


from collections import deque
n = int(input())
s = [int(x) for x in input().split()]
L = []
for i in range(0, n):
	h = []
	L.append(h)
for i in range(0, len(s)):
	if i - s[i] >= 0 and i - s[i] < n:
		L[i - s[i]].append(i)
	if i + s[i] >= 0 and i + s[i] < n:
		L[i + s[i]].append(i)
fnl = [-1] * n
q = deque()
dist = [10000000007] * n
for i in range(0, len(s)):
	if s[i] % 2 != 0:
		q.append(i)
		dist[i] = 0
while q:
	r = q.popleft()
	for i in L[r]:
		if dist[i] == 10000000007:
			dist[i] = dist[r] + 1
			q.append(i)
for i in range(0, len(s)):
	if s[i] % 2 == 0 and dist[i] != 10000000007:
		fnl[i] = dist[i]
q.clear()
dist = [10000000007] * n
for i in range(0, len(s)):
	if s[i] % 2 == 0:
		q.append(i)
		dist[i] = 0
while q:
	r = q.popleft()
	for i in L[r]:
		if dist[i] == 10000000007:
			dist[i] = dist[r] + 1
			q.append(i)
for i in range(0, len(s)):
	if s[i] % 2 != 0 and dist[i] != 10000000007:
		fnl[i] = dist[i]
print(*fnl)


from collections import deque

def bfs(st, end):
	global n
	inf = 9999999
	q = deque()
	d = [inf] * n
	for i in st:
		q.append(i)
		d[i] = 0
	while len(q) > 0:
		u = q[0]
		q.popleft()
		for k in g[u]:
			if d[k] == inf:
				d[k] = d[u] + 1
				q.append(k)
	for v in end:
		if d[v] != inf:
			ans[v] = d[v]
n = int(input())
a = list(map(int, input().split()))
e = []
o = []
g = [[] for _ in range(n)]
for i in range(n):
	if a[i] & 1:
		o.append(i)
	else:
		e.append(i)
	if i + a[i] < n:
		g[i + a[i]].append(i)
	if i - a[i] >= 0:
		g[i - a[i]].append(i)
inf = 9999999
ans = [-1 for _ in range(n)]
bfs(o, e)
bfs(e, o)
print(*ans)


import sys
import time
from collections import deque

def bfs(n, graph, startVertices, endVertices, result):
	distance = [sys.maxsize] * n
	q = deque([])
	for v in startVertices:
		distance[v] = 0
		q.append(v)
	while len(q):
		v = q.popleft()
		for adj in graph[v]:
			if distance[adj] == sys.maxsize:
				distance[adj] = distance[v] + 1
				q.append(adj)
	for v in endVertices:
		if distance[v] != sys.maxsize:
			result[v] = distance[v]

def play(n, arr):
	even = []
	odd = []
	graph = [[] for i in range(0, n)]
	for i in range(0, n):
		a = arr[i]
		if a % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
		leftIndex = i - a
		if leftIndex >= 0:
			graph[leftIndex].append(i)
		rightIndex = i + a
		if rightIndex < n:
			graph[rightIndex].append(i)
	result = [-1] * n
	bfs(n, graph, even, odd, result)
	bfs(n, graph, odd, even, result)
	print(*result)

def play2(n, arr):
	even = []
	odd = []
	graph = [[] for i in range(0, n)]
	for i in range(0, n):
		a = arr[i]
		if a % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
		leftIndex = i - a
		if leftIndex >= 0:
			graph[leftIndex].append(i)
		rightIndex = i + a
		if rightIndex < n:
			graph[rightIndex].append(i)
	result = [-1] * n
	bfs(n, graph, even, odd, result)

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	play(n, arr)
main()


n = int(input())
m = list(map(int, input().split()))
from collections import defaultdict, deque
g = defaultdict(list)
a = [float('inf')] * n
for i in range(1, n + 1):
	if i + m[i - 1] <= n:
		g[i + m[i - 1]].append(i)
	if i - m[i - 1] > 0:
		g[i - m[i - 1]].append(i)
q = deque()
vis = [0] * n
for i in range(n):
	if m[i] % 2:
		q.append((i + 1, 0))
		vis[i] = 1
while q:
	(cur, d) = q.popleft()
	for i in g[cur]:
		if m[i - 1] % 2 == 0:
			a[i - 1] = min(a[i - 1], d + 1)
		if vis[i - 1] == 0:
			q.append((i, d + 1))
			vis[i - 1] = 1
p = deque()
vis = [0] * n
for i in range(n):
	if m[i] % 2 == 0:
		p.append((i + 1, 0))
		vis[i] = 1
while p:
	(cur, d) = p.popleft()
	for i in g[cur]:
		if m[i - 1] % 2:
			a[i - 1] = min(a[i - 1], d + 1)
		if vis[i - 1] == 0:
			p.append((i, d + 1))
			vis[i - 1] = 1
for i in range(n):
	if a[i] == float('inf'):
		a[i] = -1
print(*a)


class Graph:

	def __init__(self, V):
		self.V = V
		self.adj_list = [[] for u in range(V)]
		self.edges = []

	def add_edge(self, edge):
		self.edges.append(edge)

	def add_neighdor(self, v1, v2):
		self.adj_list[v1].append(v2)

	def get_neighdor(self, v):
		return self.adj_list[v]
input()
n = map(int, input().split())
n = list(n)
ans = len(n) * [-1]
queue = []
graph = Graph(len(n))
for i in range(len(n)):
	for v in (i - n[i], i + n[i]):
		if 0 <= v < len(n):
			if n[i] % 2 != n[v] % 2:
				ans[i] = 1
				queue.append(i)
			else:
				graph.add_edge((v, i))
				graph.add_neighdor(v, i)
index = 0
while len(queue) > index:
	v = queue[index]
	for i in graph.get_neighdor(v):
		if ans[i] == -1:
			ans[i] = ans[v] + 1
			queue.append(i)
	index += 1
print(*ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
n = ii()
ls = ll()
top = []
par = [[] for _ in range(n)]
ans = [-1] * n
vis = set()
for i in range(n):
	(a, b) = (i - ls[i], i + ls[i])
	if a >= 0:
		if ls[i] & 1 ^ ls[a] & 1:
			top.append(i)
			ans[i] = 1
			vis.add(i)
			continue
		par[a].append(i)
	if b < n:
		if ls[i] & 1 ^ ls[b] & 1:
			top.append(i)
			ans[i] = 1
			vis.add(i)
			continue
		par[b].append(i)
x = len(top)
i = 0
while i < len(top):
	el = top[i]
	i += 1
	for p in par[el]:
		if p in vis:
			continue
		vis.add(p)
		ans[p] = ans[el] + 1
		top.append(p)
print(*ans)


import sys
input = sys.stdin.readline
import heapq

def dijkstra(start: int, graph: list) -> list:
	INF = 10 ** 18
	n = len(graph)
	dist = [INF] * n
	dist[start] = 0
	q = [(0, start)]
	cost = 1
	while q:
		(d, v) = heapq.heappop(q)
		if dist[v] < d:
			continue
		for nxt_v in graph[v]:
			if dist[v] + cost < dist[nxt_v]:
				dist[nxt_v] = dist[v] + cost
				heapq.heappush(q, (dist[nxt_v], nxt_v))
	return dist
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 18
rev_graph = [[] for i in range(n + 1)]
for v in range(n):
	nxt_vs = [v - a[v], v + a[v]]
	for nxt_v in nxt_vs:
		if not 0 <= nxt_v < n:
			continue
		if a[v] % 2 == a[nxt_v] % 2:
			rev_graph[nxt_v].append(v)
		else:
			rev_graph[n].append(v)
dist = dijkstra(n, rev_graph)
for i in range(n):
	if dist[i] == INF:
		dist[i] = -1
print(*dist[0:n])


import sys
import math
import itertools
import heapq
import collections
import bisect
import string

def input():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf')
mod = 10 ** 9 + 7
ans = 0
count = 0
pro = 1
n = int(input())
A = list(map(int, input().split()))
graph = [[] for i in range(n)]
ans = [-1] * n
que0 = collections.deque()

def newbfs():
	while que0:
		node = que0.popleft()
		for to in graph[node]:
			if ans[to] == -1:
				ans[to] = ans[node] + 1
				que0.append(to)
for i in range(n):
	t = False
	if i + A[i] < n:
		if A[i] % 2 != A[i + A[i]] % 2:
			ans[i] = 1
			t = True
		graph[i + A[i]].append(i)
	if 0 <= i - A[i]:
		if A[i] % 2 != A[i - A[i]] % 2:
			ans[i] = 1
			t = True
		graph[i - A[i]].append(i)
	if t:
		que0.append(i)
newbfs()
print(*ans)


from collections import deque
n = int(input())
a = list(map(int, input().split()))
d = [-1] * n
nb = [[] for i in range(n)]
for i in range(n):
	for j in [i - a[i], i + a[i]]:
		if 0 <= j < n:
			if a[i] & 1 == a[j] & 1:
				nb[j].append(i)
			else:
				d[i] = 1
queue = deque()
for i in range(n):
	if d[i] == 1:
		queue.append(i)
while len(queue) > 0:
	cur = queue.popleft()
	for x in nb[cur]:
		if d[x] == -1:
			d[x] = d[cur] + 1
			queue.append(x)
print(*d)


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

def go(parity):
	que = list(filter(lambda x: a[x] % 2 == parity, range(n)))
	index = 0
	v = [None] * n
	done = [False] * n
	for i in que:
		done[i] = True
		v[i] = 0
	while index < len(que):
		curr = que[index]
		for e in edges[curr]:
			if not done[e]:
				v[e] = v[curr] + 1
				done[e] = True
				que.append(e)
		index += 1
	return v
edges = [[] for i in range(n)]
for (i, aa) in enumerate(a):
	if i - aa >= 0:
		edges[i - aa].append(i)
	if i + aa < n:
		edges[i + aa].append(i)
v0 = go(0)
v1 = go(1)
res = [v0[i] if a[i] % 2 else v1[i] for i in range(n)]
res = [-1 if rr is None else rr for rr in res]
print(' '.join(map(str, res)))


from collections import deque
N = int(input())
a = list(map(int, input().split()))
adj0 = [[] for _ in range(N)]
adj1 = [[] for _ in range(N)]
que0 = deque()
que1 = deque()
for i in range(N):
	ai = a[i]
	if ai % 2 == 0:
		que0.append(i)
		if i + ai < N:
			adj0[i + ai].append(i)
		if i - ai >= 0:
			adj0[i - ai].append(i)
	else:
		que1.append(i)
		if i + ai < N:
			adj1[i + ai].append(i)
		if i - ai >= 0:
			adj1[i - ai].append(i)
ans0 = [0] * N
ans1 = [0] * N
while que1:
	v = que1.popleft()
	for u in adj0[v]:
		if ans0[u] == 0:
			ans0[u] = ans0[v] + 1
			que1.append(u)
while que0:
	v = que0.popleft()
	for u in adj1[v]:
		if ans1[u] == 0:
			ans1[u] = ans1[v] + 1
			que0.append(u)
ans = [-1] * N
for i in range(N):
	if a[i] % 2 == 0:
		if ans0[i] > 0:
			ans[i] = ans0[i]
	elif ans1[i] > 0:
		ans[i] = ans1[i]
print(*ans)


from collections import deque
import sys
input = sys.stdin.buffer.readline
n = int(input())
x = list(map(int, input().split()))
co = [-1 for i in range(n)]
invind = [[] for i in range(n)]
seen = set()
tosee = set()
level = 1
for i in range(n):
	ok = False
	if x[i] + i < n:
		invind[x[i] + i].append(i)
		if (x[x[i] + i] - x[i]) % 2 == 1:
			co[i] = 1
			tosee.add(i)
			ok = True
	if i - x[i] >= 0:
		invind[i - x[i]].append(i)
		if not ok and (x[i - x[i]] - x[i]) % 2 == 1:
			co[i] = 1
			tosee.add(i)
coooo = 2
while tosee:
	later = list(tosee)
	tosee = set()
	for x in later:
		seen.add(x)
		for zz in invind[x]:
			if zz not in seen:
				tosee.add(zz)
				if co[zz] == -1:
					co[zz] = coooo
	coooo += 1
print(' '.join(map(str, co)))


from collections import deque
n = int(input())
a = [int(i) for i in input().split()]
graph = [[] for i in range(n)]
ans = [-1] * n
for i in range(n):
	for j in [i - a[i], i + a[i]]:
		if 0 <= j < n:
			if a[i] % 2 == a[j] % 2:
				graph[j].append(i)
			else:
				ans[i] = 1
q = deque()
for i in range(n):
	if ans[i] == 1:
		q.append(i)
while len(q) > 0:
	curr = q.popleft()
	for i in graph[curr]:
		if ans[i] == -1:
			ans[i] = ans[curr] + 1
			q.append(i)
print(*ans)


n = int(input())
odd = []
even = []
g = [[] for i in range(n)]
l = [int(x) for x in input().split()]
ans = [-1 for i in range(n)]

def bfs(start, end):
	d = [-2 for i in range(n)]
	q = []
	qi = 0
	for i in range(len(start)):
		d[start[i]] = 0
		q.append(start[i])
	while len(q) != qi:
		f = q[qi]
		qi += 1
		for daughter in g[f]:
			if d[daughter] == -2:
				d[daughter] = 1 + d[f]
				q.append(daughter)
	for i in range(n):
		if d[i] != -2 and d[i] != 0:
			ans[i] = d[i]
	return ans
for i in range(n):
	left = i - l[i]
	right = i + l[i]
	if left >= 0:
		g[left].append(i)
	if right < n:
		g[right].append(i)
	if l[i] & 1:
		odd.append(i)
	else:
		even.append(i)
bfs(odd, even)
bfs(even, odd)
print(*ans)


from sys import stdin
from collections import deque
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
from collections import deque
n = int(input())
l = list(map(int, input().split()))
ans = [-1] * n
hash = defaultdict(list)
que = deque([])
for (i, x) in enumerate(l):
	t = False
	if i + x < n:
		if l[i + x] % 2 != l[i] % 2:
			ans[i] = 1
			t = True
		hash[i + x].append(i)
	if i - x >= 0:
		if l[i - x] % 2 != l[i] % 2:
			ans[i] = 1
			t = True
	hash[i - x].append(i)
	if t:
		que.append(i)
while len(que) > 0:
	now = que.popleft()
	for i in hash[now]:
		if ans[i] == -1:
			ans[i] = ans[now] + 1
			que.append(i)
print(*ans)


import sys
from sys import stdin
from collections import deque
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
lis = [[] for i in range(n)]
d = [float('inf')] * n
q = deque([])
for i in range(n):
	if 0 <= i - a[i] and a[i] % 2 != a[i - a[i]] % 2 or (i + a[i] < n and a[i] % 2 != a[i + a[i]] % 2):
		d[i] = 1
		q.append(i)
	else:
		if i - a[i] >= 0:
			lis[i - a[i]].append(i)
		if i + a[i] < n:
			lis[i + a[i]].append(i)
while q:
	v = q.popleft()
	for nex in lis[v]:
		if d[nex] > d[v] + 1:
			d[nex] = d[v] + 1
			q.append(nex)
for i in range(n):
	if d[i] == float('inf'):
		d[i] = -1
print(*d)


from collections import deque
n = int(input())
arr = list(map(int, input().split(' ')))
even = []
odd = []
graph = dict(((i, list()) for i in range(n)))
ans = {}

def bfs(start, end):
	queue = deque()
	distances = {}
	for s in start:
		queue.append(s)
		distances[s] = 0
	while queue:
		idx = queue.popleft()
		for to in graph[idx]:
			if to not in distances:
				distances[to] = distances[idx] + 1
				queue.append(to)
			else:
				assert distances[to] <= distances[idx] + 1
	for e in end:
		if e in distances:
			ans[e] = distances[e]
for (idx, a) in enumerate(arr):
	if a % 2 == 0:
		even.append(idx)
	else:
		odd.append(idx)
	left = idx - a
	right = idx + a
	if left >= 0:
		graph[left].append(idx)
	if right < n:
		graph[right].append(idx)
bfs(even, odd)
bfs(odd, even)
for i in range(n):
	if i not in ans:
		ans[i] = -1
	print(ans[i], end=' ')
print()