Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

Return the length of the shortest subarray to remove.

A subarray is a contiguous subsequence of the array.

&nbsp;
Example 1:

Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].


Example 2:

Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].


Example 3:

Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 105
	0 &lt;= arr[i] &lt;= 109


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        i = 0
        while i < n-1 and arr[i+1] >= arr[i]:
            i += 1
        
        if i == n-1:
            return 0
        
        j = n-1
        while j >= 0 and arr[j-1] <= arr[j]:
            j -= 1
        
        ans = min(n, n-i-1, j)
        
        for l in range(i+1):
            r = j
            while r < n and arr[r] < arr[l]:
                r += 1
            ans = min(ans, r-l-1)
        
        return ans
class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int firstLast=0,lastFirst=arr.length-1;
        for(;firstLast<arr.length-1;firstLast++){
            if(arr[firstLast]>arr[firstLast+1]) break;
        }
		//Base case for a non-decreasing sequence
        if(firstLast==arr.length-1) return 0;
        for( ;lastFirst>0;lastFirst--){
            if(arr[lastFirst]<arr[lastFirst-1]) break;
        }
		//Possibilities 1 or 2 as mentioned above
        int minLength=Math.min(arr.length-firstLast-1,lastFirst);
        for(;firstLast>=0;firstLast--){
            for(int i=lastFirst;i<arr.length;i++){
                if(arr[firstLast]>arr[i]) continue;
                minLength = Math.min(minLength,i-firstLast-1);
                break;
            }
        }
        return minLength;
    }
}
// itne me hi thakk gaye?
class Solution {
public:
    bool ok(int &size, vector<int> &pref, vector<int> &suff, vector<int> &arr, int &n) {
        for(int start=0; start<=n-size; start++) {
            int end = start + size - 1;
            int left = (start <= 0) ? 0 : pref[start-1];
            int right = (end >= n-1) ? 0 : suff[end+1];
            int le = (start <= 0) ? -1e9+2 : arr[start-1];
            int re = (end >= n-1) ? 1e9+2 : arr[end+1];
            if (left + right == n-size && le <= re) {
                return true;
            }
        }
        return false;
    }
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();
        if (!n || n==1) return 0;
        vector<int> pref(n, 1);
        vector<int> suff(n, 1);
        for(int i=1; i<n; i++) {
            if (arr[i] >= arr[i-1]) pref[i] = pref[i-1]+1;
        }
        for(int i=n-2; i>=0; i--) {
            if (arr[i] <= arr[i+1]) suff[i] = suff[i+1]+1;
        }
        int low = 0;
        int high = n-1;
        while(low < high) {
            int mid = (low + high)/2;
            if(ok(mid, pref, suff, arr, n)) high = mid;
            else low = mid+1;
            if(high - low == 1) break;
        }
        if (ok(low, pref, suff, arr, n)) return low;
        return high;
    }
};
var findLengthOfShortestSubarray = function(arr) {
    const n = arr.length;
    
    if (n <= 1) {
        return 0;
    }
    
    let prefix = 1;
    
    while (prefix < n) {
        if (arr[prefix - 1] <= arr[prefix]) {
            prefix++;
        } else {
            break;
        }
    }
    
    if (prefix === n) {
        return 0;
    }
    
    let suffix = 1;
    
    while (suffix < n) {
        const i = n - 1 - suffix;
        
        if (arr[i] <= arr[i + 1]) {
            suffix++;
        } else {
            break;
        }
    }

    let res = Math.min(n - prefix, n - suffix);
    let left = 0;
    let right = n - suffix;

    while (left < prefix && right < n) {
        if (arr[left] <= arr[right]) {
            res = Math.min(res, right - left - 1);
            left++;
        } else {
            right++;
        }
    }

    return res;
};
Shortest Subarray to be Removed to Make Array Sorted