Bước Nhảy Đổi Tính Chẵn Lẻ · canuc80k3026

Cho mảng số nguyên dương $a_{1}, a_{2}, \dots, a_{n}$ . Khi đang đứng ở vị trí $i$ , bạn có thể thực hiện một bước nhảy tới:

vị trí $i - a_{i}$ , nếu vị trí này vẫn thuộc đoạn $1, \dots, n$ ;
vị trí $i + a_{i}$ , nếu vị trí này vẫn thuộc đoạn $1, \dots, n$ .

Với từng vị trí bắt đầu $i$ , hãy tìm số bước ít nhất để tới một vị trí $j$ mà $a_{j}$ khác tính chẵn lẻ với $a_{i}$ . Nếu không tồn tại cách đi như vậy, kết quả của vị trí $i$ là $- 1$ .

Input

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Output

In $n$ số nguyên. Số thứ $i$ là số bước ít nhất cần tìm cho vị trí $i$ , hoặc $- 1$ nếu không thể tới giá trị có tính chẵn lẻ đối lập.

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq a_{i} \leq n$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

5
1 2 1 2 1

Output

1 -1 1 -1 1

Giải thích: Các vị trí $1, 3, 5$ đều nhảy một bước tới một giá trị chẵn. Từ vị trí $2$ hoặc $4$ , mọi vị trí có thể tới đều mang giá trị chẵn nên kết quả là $- 1$ .

Ý tưởng: Xem mỗi vị trí là một đỉnh. Từ i có nhiều nhất hai cạnh đi tới i-a_i và i+a_i. Nếu chạy BFS riêng cho từng vị trí thì tổng thời gian có thể là bậc hai.
Ý tưởng: Đảo chiều toàn bộ cạnh. Trong đồ thị đảo, một đường từ vị trí đích j tới i tương ứng đúng một đường cùng số bước từ i tới j trong đồ thị ban đầu.
Ý tưởng: Chạy hai BFS nhiều nguồn trên đồ thị đảo:
Ý tưởng: BFS bắt đầu đồng thời từ mọi vị trí có giá trị chẵn;
Ý tưởng: BFS bắt đầu đồng thời từ mọi vị trí có giá trị lẻ.
Ý tưởng: Với vị trí mang giá trị lẻ, lấy khoảng cách tới tập nguồn chẵn; với vị trí mang giá trị chẵn, lấy khoảng cách tới tập nguồn lẻ. Đỉnh không được thăm có kết quả -1.
Ý tưởng: Đồ thị có không quá 2n cạnh, nên độ phức tạp là O(n) thời gian và bộ nhớ.