An array is called almost sorted if you can delete at most one element and be left with a strictly increasing sequence. For example, [2,1,7] is almost sorted because removing 1 gives [2,7], which is ascending. On the other hand, [4,2,1] is not almost sorted — no single deletion produces an increasing list; you would need to remove at least two elements.
You are given an array arr containing distinct integers. Return the minimum number of elements you must remove so that the remaining array becomes almost sorted.
Example 1:
Input: arr = [3,1,4,2]
Output: 1
Explanation: After removing 2, the leftover array [3,1,4] is almost sorted because deleting 3 yields [1,4].
Example 2:
Input: arr = [1,5,2,6,3,7,4]
Output: 2
Explanation: One optimal way is to delete 6 and 4, keeping [1,5,2,3,7]. This array is almost sorted: removing 5 produces [1,2,3,7]. It is impossible to keep more than 5 elements.
Example 3:
Input: arr = [10,5]
Output: 0
Explanation: The array is already almost sorted — deleting 5 leaves [10], a trivially sorted single-element array, so zero removals are needed.
Constraints:
1 <= arr.length <= 100,000-1,000,000,000 <= arr[i] <= 1,000,000,000arr are distinct.O(n log n) worst-case time.