Cho số nguyên dương ~n~ và mảng ~a[1..n]~. Với mỗi phần tử, tìm phần tử nhỏ hơn đầu tiên bên trái.

Dữ liệu vào:

• Dòng 1: Ghi số nguyên dương n (~1 \le n \le 10^5~)

• Ghi ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~)

  Dữ liệu ra:

• In ra phần tử nhỏ hơn đầu tiên bên trái ứng với từng phần tử ~a_i~, nếu không tìm thấy thì in ra -1.

Ví dụ

Input

5
2 1 2 4 3

Output

-1 -1 1 2 2