Cho dãy a có n số nguyên dương a[1..n].

Với mỗi a[i], cho biết giá trị của phần tử lớn hơn a[i], ở bên trái a[i] và gần i nhất. Nếu không có giá trị nào lớn hơn a[i] thì viết -1.

Giới hạn:

• n ≤ 10^6
• a[i] ≤ 10^9

Ví dụ

Input

5
4 5 2 3 1

Output

-1 -1 5 5 3