Cho số nguyên dương ~ n ~ và dãy số nguyên ~ a_1, a_2, …., a_n ~. Ở mỗi bước di chuyển, bạn có thể nhảy từ vị trị ~ i ~ đến vị trí ~ i-a_i ~ nếu ~ i-a_i ≥ 1 ~ hoặc vị trí ~ i+a_i ~ nếu ~ i+a_i ≤ n ~.

Yêu cầu: với mỗi vị trí ~ i ~ ~ (i = 1…n ) ~ trong dãy số hãy cho biết cần ít nhất bao nhiêu bước để di chuyển từ vị trí ~ i ~ đến vị trí ~ j ~ sao cho hai số ~ a_i ~ và ~ a_j ~ chẵn lẽ đối lập nhau (nghĩa là nếu ~ a_i ~ chẵn thì ~ a_j ~ lẻ và ngược lại)

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~ n ~ ~ 1 ≤ n ≤ 10^5 ~;
• Dòng tiếp theo ghi lần lượt ~ n ~ số nguyên là ~ a_1, a_2, …, a_n ~ ~ 1 ≤ a_i ≤ n ~

Kết quả

In ~ n ~ số nguyên ~ d_1, d_2, …, d_n ~ trong đó ~ d_i ~ là số bước ít nhất để di chuyển từ vị trí thứ ~ i ~ theo yêu cầu bài toán. Nếu tại vị trí thứ ~ i ~ không có cách di chuyển thì ~ d_i = -1 ~.

Ví dụ:

Input 1

6
1 4 3 1 4 2 

Output 1

1 2 1 1 1 1