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ử lớn hơn đầu tiên bên phả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ử lớn hơn đầu tiên bên phả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

4 2 4 -1 -1