A row of boxes has heights heights. A cut before index i (1 <= i < n) is orderly if every box on the left is no taller than every box on the right, i.e. max(heights[0..i-1]) <= min(heights[i..n-1]). Count the orderly cuts.
Examples
Input: heights = [1, 3, 2, 5, 4, 6]
Output: 3
Explanation: cuts before index 1 (1 | 3 2 5 4 6), before index 3 (1 3 2 | 5 4 6) and before index 5 (1 3 2 5 4 | 6).
Input: heights = [3, 2, 1]
Output: 0
Input: heights = [2, 2]
Output: 1
Constraints
1 <= len(heights) <= 10**5-10**6 <= heights[i] <= 10**6- Target complexity: O(n) time. Recomputing max and min for every cut is too slow.
Goals
- Precompute a suffix minimum array
- Combine a running prefix maximum with the suffix array to test each cut in O(1)