Cho số nguyên dương \(n\) và dãy số nguyên \(a_{1},a_{2},\ldots.,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} \geq 1\) hoặc vị trí \(i + a_{i}\) nếu \(i + a_{i} \leq n\).

Yêu cầu: với mỗi vị trí \(i\ (i = 1\ldots 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\);

+ Dòng tiếp theo ghi lần lượt \(n\) số nguyên là \(a_{1},a_{2},\ldots,a_{n}\)

Giới hạn:

+ \(1 \leq n \leq 10^{5}\)

+ \(1 \leq a_{i} \leq n\)

Kết quả: In \(n\) số nguyên \(d_{1},d_{2},\ldots,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ụ: