Dựng cây (Tree Construction)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $a_1,a_2,\ldots,a_n$ gồm các số nguyên phân biệt. Dãy được dùng để dựng một cây tìm kiếm nhị phân theo đúng thứ tự sau:

$a_1$ trở thành gốc.

Với mỗi $i$ từ $2$ đến $n$, bắt đầu tại gốc. Nếu $a_i$ nhỏ hơn khóa ở nút hiện tại thì chuyển sang con trái; nếu $a_i$ lớn hơn thì chuyển sang con phải. Nếu nhánh cần chuyển tới đang rỗng, tạo nút mới mang khóa $a_i$ tại vị trí đó và kết thúc lần chèn.

Với mỗi phần tử $a_i$ từ phần tử thứ hai trở đi, hãy xác định khóa nằm trong nút cha trực tiếp của nút vừa được tạo.

Input

Dòng đầu chứa số nguyên $n$.

Dòng thứ hai chứa $n$ số nguyên phân biệt $a_1,a_2,\ldots,a_n$ theo thứ tự chèn.

Output

In trên một dòng $n-1$ số. Số thứ $i-1$ là khóa của nút cha của nút mang khóa $a_i$, với mọi $2\le i\le n$.

Các số được cách nhau bởi một dấu cách.

Subtask

Subtask 1 (20 điểm): $2\le n\le 20$.

Subtask 2 (30 điểm): $2\le n\le 5000$.

Subtask 3 (50 điểm): $2\le n\le 100000$, $1\le a_i\le 10^9$.

Trong tất cả các subtask, mọi $a_i$ phân biệt.

Ví dụ

Input

5
4 2 3 1 6

Output

4 2 2 4

Giải thích

$4$ là gốc. Khi chèn $2$, nó trở thành con trái của $4$, nên cha của $2$ là $4$.

Tiếp theo, $3$ đi từ $4$ sang trái tới $2$ rồi trở thành con phải của $2$, nên cha của $3$ là $2$. Khóa $1$ trở thành con trái của $2$, còn $6$ trở thành con phải của $4$.

Vì vậy dãy khóa cha theo thứ tự chèn $a_2,a_3,a_4,a_5$ là 4 2 2 4.