Challenge: Next Greater Number

Lab Python Intermediate 20 points

Read a list of numbers. For each one, print the next number to its right that is bigger, or -1. Use a monotonic stack (O(n)).

Input

One line of whole numbers.

Output

The answers separated by spaces.

Example

Input

4 5 2 25

Output

5 25 25 -1

Sample input available Sample output available

Editor

Python

Hints

Keep a stack of indexes still waiting for an answer.

When a bigger number arrives, pop and answer everything smaller on top.

Solution explanation

Every index is pushed and popped at most once: O(n) total.

Show solution

a = list(map(int, input().split()))
ans = [-1] * len(a)
stack = []
for i, x in enumerate(a):
    while stack and a[stack[-1]] < x:
        ans[stack.pop()] = x
    stack.append(i)
print(" ".join(map(str, ans)))

Output

Answer