604. The Shortest Span to Sort
Given n integers, find the shortest contiguous stretch such that sorting
only that stretch makes the whole array non-decreasing. Print its length, or 0
if the array is already sorted.
Sorting a copy and comparing works and costs a sort. One pass from each end does not.
From the LEFT, track the running maximum. Any position holding a value smaller than the running maximum must be inside the stretch, and the last such position is its right edge. From the RIGHT, track the running minimum: any position holding a value larger than it is inside, and the last such position is the left edge.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ a[i] ≤ 1000000000`
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print one integer: the length of the shortest stretch that must be sorted, or 0 if the array is already non-decreasing.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.