Next Smaller Element

Mediumjavapythonccppjavascript

For every element of an array, find the first element to its right that is strictly smaller. 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 smaller element for each position, separated by single spaces.

Example 1

Input

5
4 8 5 2 25

Output

2 5 2 -1 -1

Explanation: The first smaller value to the right of 4 is 2; no smaller value exists after 2 or 25.

Related Problems