JOI có \(N\) quân cờ vây, được đánh số từ \(1\) đến \(N\). Màu của mỗi quân cờ được biểu diễn bằng một số nguyên từ \(1\) đến \(10^9\). Ban đầu, quân cờ \(i\) (\(1 \le i \le N\)) có màu \(A_i\).

JOI sẽ thực hiện \(N\) thao tác để xếp các quân cờ thành một hàng trên bàn. Thao tác thứ \(i\) (\(1 \le i \le N\)) được thực hiện theo thứ tự sau:

1. Đặt quân cờ \(i\) ngay bên phải quân cờ \(i - 1\). Riêng khi \(i = 1\), đặt quân cờ \(1\) lên bàn.
2. Nếu trong các quân cờ \(1, 2, \ldots, i - 1\) có quân cờ mang màu hiện tại giống với quân cờ \(i\), gọi \(j\) là số hiệu lớn nhất trong số các quân cờ đó. Khi ấy, đổi màu của tất cả các quân cờ \(j + 1, j + 2, \ldots, i - 1\) thành \(A_i\).

Để kiểm tra mình có thực hiện đúng các thao tác hay không, JOI muốn biết trước màu của các quân cờ sau khi thực hiện xong tất cả các thao tác.

Cho thông tin về các quân cờ, hãy tìm màu của từng quân cờ sau \(N\) thao tác.

Dữ liệu vào

Dữ liệu vào có dạng:

N
A_1
A_2
...
A_N

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) (\(1 \le i \le N\)) chứa màu của quân cờ \(i\) sau \(N\) thao tác.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(25\) điểm: \(N \le 2000\).
2. \(35\) điểm: \(A_i \le 2\) với mọi \(1 \le i \le N\).
3. \(40\) điểm: Không có ràng buộc bổ sung.

Ví dụ

6
1
2
1
2
3
2

1
1
1
2
2
2

10
1
1
2
2
1
2
2
1
1
2

1
1
1
1
1
1
1
1
1
2

Nguồn

Bản dịch tiếng Việt từ đề chính thức tiếng Anh, đối chiếu với đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.