Next Greater Element
For each element in an array, find the next element to its right that is greater, using a monotonic stack.
Input format
The first line contains N. The second line contains N integers.
Output format
For each element print the first element to its right that is strictly greater, or -1 if none exists — space-separated, in input order.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
4
1 3 2 4Expected output
3 4 4 -1Example 2
Input
3
3 2 1Expected output
-1 -1 -1