Next Greater to the Right

Difficulty: 1400 3500 ms 128 MB

stack

For every element print the first strictly greater element to its right, or −1 if none exists.

Input: the first line has N; the second line has N integers.

Output: N integers: the next greater element of each position.

Constraints:

• 1 ≤ N ≤ 10⁵
• −10⁹ ≤ a_i ≤ 10⁹

Sample Tests

4
2 1 2 4

4 2 4 -1

3
3 2 1

-1 -1 -1

Read the Editorial