Next Greater Element

Medium#arrays #stack #monotonic-stack· solved by 0 · time limit 2.0 s

For each element, print the first element to its right that is strictly greater, or -1. A monotonic stack solves it in $O(n)$ .

Input

$n$ , then $n$ integers.

$n$ answers.

$1 \le n \le 10^5$

Input

4
4 5 2 25

Output

5 25 25 -1

Input

4
13 7 6 12

Output

-1 12 12 -1