Monotonic Stack - Classic Problems | Repovive

CLS34. Monotonic Stack

1s256 MB

Given an array of $n$ integers, for each element find the first greater element to its right.

If no greater element exists to the right, output $-1$ for that position.

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

$nge_1 \quad nge_2 \quad \cdots \quad nge_n$

Input

5
4 5 2 10 8

Explanation

For this input, the required output is 5 10 10 -1 -1.

Output

5 10 10 -1 -1

Input

5
5 4 3 2 1

Explanation

For this input, the required output is -1 -1 -1 -1 -1.

Output

-1 -1 -1 -1 -1

Input

5
1 2 3 4 5

Explanation

For this input, the required output is 2 3 4 5 -1.

Output

2 3 4 5 -1

Given an array of $n$ integers, for each element find the first greater element to its right.

If no greater element exists to the right, output $-1$ for that position.

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

$nge_1 \quad nge_2 \quad \cdots \quad nge_n$