858. Steps Until Nothing More Is Removed

Read n values. In one STEP, look at the current row and delete every element that has a strictly larger element immediately to its left. All deletions in a step happen at the same time, using the row as it was at the start of the step, and then the survivors close up.

Repeat until a step deletes nothing. Print how many steps were performed, counting only the steps that deleted something.

5 3 4 4 7 3 6 11 8 5 11 -> 3 4 5 7 7 13 -> 0 7 1 2 3 4 5 6 -> 6

The first row goes 5 3 4 4 7 3 6 11 8 5 11 to 5 4 4 7 6 11 11 to 5 7 11 11 to 5 7 11 11, which is three steps with the third one making no change... count again: the second row still loses its 4 and 6, and the third step is the one that stops. Simulating it by hand once is worth more than reading the answer.

## Why simulating is too slow

Each step costs a full pass, and the number of steps can be n - 1, as in n, n-1, ..., 2, 1 where exactly one element leaves per step. That is O(n^2), which at n = 200000 is 4 * 10^10.

## The quantity to compute per element

For each element, define d[i] as the STEP NUMBER on which it is deleted, or 0 if it is never deleted. The answer is max(d[i]).

Element i is deleted on the first step at which its current left neighbour is strictly larger than it. Its current left neighbour changes over time: it is whichever of the earlier elements has not yet been deleted.

## The recurrence, and the stack that supports it

Sweep left to right with a stack kept DECREASING in value from the bottom up. When a[i] arrives:

cur = 0 while the stack is non-empty and the top value <= a[i]: cur = max(cur, the step number stored with the popped entry) if the stack is now empty: d[i] = 0 nothing to its left will ever be larger else: d[i] = cur + 1 push (a[i], d[i])

The elements popped are exactly the ones that a[i] outlives, since they are no larger than it. Element i cannot be deleted until every one of them is gone, which takes max(cur) steps, and then the element below them becomes i's left neighbour and deletes it on the very next step. That is the + 1.

If the stack empties, everything to the left is no larger than a[i], so i becomes the front of the row and can never be deleted.

## Why the stack must decrease, and why the comparison is loose

Decreasing, because the deleter of an element is a strictly LARGER element to its left. Something smaller or equal on the stack can never delete anything that a[i] cannot delete sooner, so it is dominated and popped.

The pop test is <=, not <: an EQUAL element does not delete a[i], but it also cannot survive longer than a[i] from i's point of view, and it must be cleared so the correct eventual neighbour is exposed. Using < leaves equal values on the stack and 5 5 5 5 5 answers 1 instead of 0.

## Related problems

Problem 849 also collapses a repeated sweep, but its per-element value is a plain difference so its stack disappears. Here the value carried on the stack is a maximum over what was popped, which is why the stack has to stay.

## Sizes and widths

Values reach 10^9 in absolute size and are only compared, never combined. Every step number is at most n, so the answer and the values carried on the stack both fit in 32 bits; the values themselves still need a type that holds 10^9.

## Cost

Time O(n), one pass with at most n pushes and n pops. Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a[i] ≤ 10^9`