Xây dựng cây nhị phân tìm kiếm

Cho một dãy $a$ gồm $n$ số nguyên đôi một khác nhau. Ta dùng dãy này để xây dựng một cây nhị phân tìm kiếm (BST) theo quy tắc sau:

1. Phần tử $a_1$ trở thành gốc của cây.
2. Lần lượt thêm các phần tử $a_2,a_3,\dots ,a_n$. Để thêm phần tử $a_i$:
   • Đặt con trỏ hiện tại tại gốc cây.
   • Nếu $a_i$ lớn hơn giá trị ở nút hiện tại thì chuyển con trỏ sang con phải, ngược lại chuyển sang con trái.
   • Nếu nút con cần đi tới chưa tồn tại thì tạo một nút mới mang giá trị $a_i$ và gắn nó vào đúng vị trí con đó, quá trình thêm $a_i$ kết thúc.

Với mỗi $i>1$, hãy cho biết giá trị được ghi ở nút cha của nút chứa $a_i$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là độ dài của dãy.
• Dòng thứ hai chứa $n$ số nguyên đôi một khác nhau $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra $n-1$ số nguyên trên một dòng, cách nhau bởi dấu cách: số thứ $i$ là giá trị ở nút cha của nút chứa $a_{i+1}$.

Ràng buộc

• $2\le n\le 100000$
• $1\le a_i\le {10}^9$
• Các giá trị $a_i$ đôi một khác nhau.

Ví dụ