Next Greater Element (Monotonic Stack)

core

This is the scaffold behind every "next greater / next warmer / next taller" problem. Implement next_greater(a) returning, for each index i, the index of the first element to its right that is strictly greater than a[i], or -1 if no such element exists. Equal values never count as greater; a later element tied with a[i] does not resolve it. The intended tool is a stack of candidate indices whose values decrease from bottom to top: push each index; whenever the current value beats the index on top of the stack, pop it and record the current index as its answer.

Example: next_greater({3, 1, 3, 2, 3}) returns {-1, 2, -1, 4, -1}.

Index 1 (value 1) is resolved by index 2 (value 3), the first strictly-greater value to its right → 2.
Index 0 and index 2 both hold a 3; every 3 later in the array is equal, never greater, so both stay -1.
Index 3 (value 2) is resolved by index 4 (value 3) → 4.
Index 4 has nothing to its right → -1.

Tests include a case with n up to 2*10^5, so your solution must run in O(n) total, not O(n^2).

Input format: each test in tests/*.in is laid out as:

Line 1: the mode letter L.
Line 2: n, the array length.
Line 3: the n values, space-separated.

A performance test is instead the single line G 200000 111 (mode G): the harness builds an adversarial length-n array itself from the seed and compares a checksum of next_greater's result, so your function still receives an ordinary array.

Test 05.in reads:

L
1
7

This is a one-element array; nothing lies to the right of 7, so the answer is -1.

Where you'll use it:

✦ Solution & editorial unlock with the pass.