Next Greater Element

Mediumjavapythonccppjavascript

For every element of an array, find the first element to its right that is strictly greater. If no such element exists, use -1.

Input Format

The first line contains an integer N. The second line contains N space-separated integers.

Output Format

Print N values, the next greater element for each position, separated by single spaces.

Example 1

Input

4
4 5 2 10

Output

5 10 10 -1

Explanation: For 4 the next greater value is 5; for 10 there is none.

Related Problems