Next Greater Element

You are given an array of integers.

For each position $i$, find the first element to the right of $i$ that is strictly greater than $a_i$. If no such element exists, output -1 for that position.

Input

The first line contains an integer $n$, the size of the array.

The second line contains $n$ integers: $a_1, a_2, \ldots, a_n$.

Output

Print $n$ integers, where the $i$-th integer is the next greater element to the right of $a_i$, or -1 if none exists.

Constraints

• $1 \le n \le 2 \cdot 10^5$
• $-10^9 \le a_i \le 10^9$

Example 1

5
4 5 2 10 8

5 10 10 -1 -1

Example 2

4
13 7 6 12

-1 12 12 -1

Example 3

4
3 3 3 3

-1 -1 -1 -1