Shortest Subarray to be Removed to Make Array Sorted

Find the first index left where the nondecreasing prefix stops, and the first index right of the nondecreasing suffix. If left >= right, the array is already sorted. A valid answer initially removes either the suffix after left or the prefix before right. Improve it by keeping i in the sorted prefix and moving j through the sorted suffix. When arr[i] <= arr[j], those two pieces can remain together, so minimize j-i-1 and advance i; otherwise advance j to find a suffix value large enough. The prefix and suffix are each monotonic, so neither pointer ever moves backward. Handle duplicates with <=, and include removing all but one element as a permitted fallback. The scan takes O(n) time and O(1) extra space. Explain that the kept elements are two sorted runs whose boundary must also be sorted.