477. The Widest Ramp

A ramp is a pair of indices i < j with a[i] <= a[j]. Print the largest j - i over all ramps, or 0 if there is none.

6 0 8 2 1 5 -> 4 i = 1 (value 0), j = 5 (value 5) 5 4 3 2 1 -> 0 no pair rises

The comparison is <=, so equal values form a ramp. 1 1 answers 1 and 3 3 3 answers 2. A solution using strict < answers 0 on both, and that is the single most common mistake here.

## Why every left endpoint is not worth considering

Index i can be discarded as a left endpoint if some earlier index holds a value that is at most a[i], because that earlier index is a better start: it pairs with every j that i pairs with, and it is further left.

So the only useful left endpoints are the positions where the running minimum strictly decreases. Collect them left to right, and their VALUES are strictly decreasing by construction.

6 0 8 2 1 5 -> candidate starts at indices 0 and 1, values 6 and 0

## Matching them from the right

Now walk j from the right end leftwards. The candidate list has strictly decreasing values, so its LAST entry is the smallest. While that last entry's value is at most a[j], it forms a ramp with j, and since we are sweeping j downwards this j is the furthest right partner that entry will ever see. Record the width and discard the entry.

Each candidate is pushed once and discarded once, so the whole thing is O(n) after the first pass.

The subtle part is why discarding is safe. Once an entry has been matched with the current j, any later j in the sweep is SMALLER, so it could only give a narrower ramp. Nothing is lost.

## The alternative worth knowing

Sorting the indices by value, breaking ties by index, and then sweeping while tracking the smallest index seen gives the same answer in O(n log n) and is easier to get right under pressure. Both are acceptable; the linear one is the better story.

## Boundaries

A single element has no pair, so the answer is 0. 2 1 also answers 0, and 1 2 3 4 answers 3. Widths are at most n - 1 and fit comfortably in 32 bits.

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ value ≤ 1000000000`