You are given an array ~A~ of ~N~ integers. For every position ~i~ (from ~0~ to ~N-1~), find the nearest greater value to its right. That is, find the first element ~A[j]~ such that ~j > i~ and ~A[j] > A[i]~.

If no such element exists, the answer for that position is ~-1~.

Input Format

The first line contains a single integer ~N~. The second line contains ~N~ space-separated integers representing the array ~A~.

Output Format

Print ~N~ space-separated integers, where the ~i~-th integer is the nearest greater value to the right of ~A[i]~. Print ~-1~ if no such value exists.

Example

Input

5
4 5 2 10 8

Output

5 10 10 -1 -1

Constraints

• ~1 \le N \le 200000~
• ~1 \le A[i] \le 10^9~

Subtasks

• 50% of the tests satisfy ~N \le 2000~.
• 50% of the tests use the full constraints.