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 ≤ i - a_i) or to the position i + a_i (if i + a_i ≤ 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 ≤ n ≤ 2 ⋅ 10^5) — the number of elements in a.

The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n), where a_i is the i-th element of a.

Output

Print n integers d_1, d_2, ..., 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 
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():
    # start_time = time.time()
    n = int(input())
    # n = 200000
    arr =  list(map(int, input().split()))
    # with open('C:/Solutions/python/CodeForces/605 Div 3/w.txt', 'r') as myfile:
    #     str = myfile.read()
    # arr =  list(map(int, str.split()))

    # play2(n, arr)  
    # print(time.time() - start_time)

    # start_time = time.time()
    play(n, arr) 

    # print(time.time() - start_time)
    
main()
#play(10, [4, 5, 7, 6, 7, 5, 4, 4, 6, 4])