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

Input

5
4 5 2 10 8

Output

5 10 10 -1 -1

Example 2

Input

4
13 7 6 12

Output

-1 12 12 -1

Example 3

Input

4
3 3 3 3

Output

-1 -1 -1 -1