Next greater element

Problem

For every number in a list, find the first number to its right that is strictly greater. Print that number, or -1 if there is none.

Example 1

Input

5
4 5 2 25 7

Output

5 25 25 -1 -1

4 finds 5, 5 finds 25, 2 finds 25, 25 and 7 find nothing.

Example 2

Input

3
9 7 5

Output

-1 -1 -1

Try the problem first. Open one hint at a time.

Hint 1

Keep a stack of indexes of values still waiting for an answer.

Hint 2

A new value answers every smaller value on top of the stack.

Write your Python code, run it on the examples and submit it to hidden tests.