851. Most Pieces You Can Sort Separately
Read n values, which may repeat. Cut the row into contiguous pieces, sort each piece on its own,
and glue the pieces back together in the same order. Print the LARGEST number of pieces for which
the glued result is the whole row in sorted order.
5 4 3 2 1 -> 1
2 1 3 4 4 -> 4
1 2 3 4 5 -> 5
The second row cuts as 2 1 | 3 | 4 | 4. Note that two equal values may sit in different pieces,
which is what makes the count 4 rather than 3.
## The condition for a cut
A cut after position i is legal exactly when
max(a[0..i]) <= min(a[i+1..n-1])
because sorting cannot move a value out of its own piece, so everything on the left must already
belong on the left. Computing prefix maxima and suffix minima answers the whole problem in
O(n), and that is a perfectly good solution. It is also O(n) extra memory and it does not
generalise.
## The stack version, which is the one to learn
Sweep left to right holding the MAXIMUM of each piece formed so far, on a stack kept non-decreasing from the bottom up.
for each value x:
if the stack is non-empty and its top > x:
top = pop x belongs inside this piece
while the stack is non-empty and its top > x:
pop and it swallows the pieces behind it too
push top the merged piece keeps the larger maximum
else:
push x x starts a brand new piece
The answer is the height of the stack at the end.
## Why merging backwards is right, and why it terminates
If x is smaller than the maximum of the piece before it, then x must end up to the LEFT of
that maximum after sorting, so the two cannot be in different pieces and the pieces must merge.
The merged piece's maximum is the larger of the two, which is the old top, so that is what goes
back on the stack.
Merging may cascade: after joining, the new piece may still be smaller than the one before it, and
the same argument applies again. Each merge destroys one piece permanently, so across the whole
sweep there are at most n merges. That is the usual counting argument, with pieces instead of
indices.
## The comparison that decides equal values
Pop on top > x, strictly. With >=, two equal values are forced into the same piece and
4 4 4 4 answers 1 instead of 4. Sorting leaves equal values interchangeable, so a cut between
them is legal.
## Related problems
Problem 604 finds the single shortest stretch whose sorting fixes the whole row. This asks for the finest possible partition instead, which is the complementary question.
## Sizes and widths
Values reach 10^9 and the answer is a piece count, at most n. Only comparisons touch the values,
so 32 bits is enough for the answer; the values themselves still need a type that holds 10^9.
## Cost
Time O(n). Space O(n), the stack in the worst case holds one entry per value.
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a[i] ≤ 10^9`
Input
The first line contains one integer n.
The second line contains n integers a[0] ... a[n-1].
Output
Print one integer alone on a line: the largest number of pieces the row can be cut into so that sorting each piece separately sorts the whole row. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.