A delivery van's odometer log readings should never go down, but a glitch has corrupted part
of it. A technician will delete exactly one non-empty contiguous stretch
readings[s..e] (with 0 <= s <= e < n). The cut is clean when the readings that remain,
in their original order, never decrease (each is at least the one before it). Deleting every
reading is allowed: an empty log is clean.
Return the number of pairs (s, e) that give a clean cut.
Examples
Input: readings = [1, 2, 9, 3, 4]
Output: 10
Explanation: every cut that removes the 9 (nine of them), plus cutting [3, 4] off the end.
Input: readings = [5, 4, 3]
Output: 3
Explanation: cut [0..1] leaves [3], cut [1..2] leaves [5], cut [0..2] leaves nothing.
Input: readings = [1, 2, 3]
Output: 6
Explanation: the log is already clean, so every one of the 6 stretches can go.
Constraints
0 <= len(readings) <= 10**5-10**9 <= readings[i] <= 10**9- An empty log has no stretch to cut, so the answer is
0. Testing every(s, e)pair is O(n^2) or worse and will time out.
Goals
- See that a valid cut must leave a sorted prefix and a sorted suffix that fit together
- Count, for every kept prefix, the whole range of suffixes that can follow it