Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.
A subarray is a contiguous subsequence of the array.
Return the length of the shortest subarray to remove.
 
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.

Example 4:
Input: arr = [1]
Output: 0

 
Constraints:

1 <= arr.length <= 10^5
0 <= arr[i] <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        

Solutions:
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        if n<=1: 
            return 0
        l,r = n,-1
        
        for i in range(1,n):
            if arr[i]<arr[i-1]:
                l = i
                break
        # monotonicially increasing
        if l == n: return 0
        
        for j in range(n-2,-1,-1):
            if arr[j]>arr[j+1]:
                r = j
                break
                
        # you can delete all to the left of r (including r)
        # you can also delete all to the right of l (including l)
        ans = min(r+1,n-l)
        
        i = 0
        # sliding window, find the rightmost i for each j
        # note at all time i must be less than l
        for j in range(r+1,n):
            while i<l and arr[i] <= arr[j]:
                i += 1
            ans = min(ans,j-i)
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        s = 0
        e = n - 1
        
        while  s < (n - 1) and arr[s] <= arr[s + 1]:
            s+=1
        if(s == n - 1):
            return 0
        
        while e >= s and arr[e] >= arr[e - 1]:
            e-=1
        
        result = min(n - 1 - s, e)
        
        i = 0
        j = e
        while(i <= s and j < n):
            if arr[j] >= arr[i]:
                result = min(result, j - i - 1)
                i+=1
            else:
                j+=1
        
        return result
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        stack = [0]
        stack2 = []
        total = 0
        for i in range(1,len(arr)):
            if arr[i]>=arr[i-1]:
                stack.append(0)
            else:
                total+=1
                stack2.append(i)
                stack.append(1)
        if total==0:
            return 0
        print(stack2)
        #erase small
        def erase(i,j):
            print((i,j))
            if (i>0 and j<len(arr)-1) and arr[i-1]>arr[j+1]:
                return min(erase(i-1,j),erase(i,j+1))
            
            else:        
                return j-i+1

        if total==1:
            return erase(stack2[0],stack2[0])
        
        return erase(stack2[0],stack2[-1]-1)


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        templ = []
        tempr = []
        flag = 0
        for i in range(len(arr)-1):
            if(arr[i]>arr[i+1]):
                flag = 1
        if(flag == 0):
            return(0)
        for i in range(1,len(arr)):
            if(arr[i]>=arr[i-1]):
                templ.append(arr[i-1])
            else:
                templ.append(arr[i-1])
                break
        for i in range(len(arr)-1,0,-1):
            if(arr[i]<arr[i-1]):
                tempr.append(arr[i])
                break
            else:
                tempr.append(arr[i])
        print((templ,tempr))
        if(len(templ)==len(tempr)):
            if(len(templ) == len(arr) or len(templ) ==0):
                return(len(templ))
        print((templ,tempr))
        from bisect import bisect_right
        mmax  = max(len(templ),len(tempr))
        for i in range(len(tempr)):
            ind = bisect_right(templ,tempr[i])
            print((i,ind))
            mmax = max(mmax,ind+i+1)
        return(max(0,len(arr) - (mmax)))
        
    


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if len(arr) < 2:
            return 0
        for i1 in range(len(arr)-1):
            if arr[i1+1] >= arr[i1]:
                continue
            else:
                break
        #arr[0] - arr[i1] is increasing and arr[i1+1] < arr[i1]
        #if overall sorted
        if arr[-2] <= arr[-1] and i1 == len(arr)-2:
            return 0
        for i2 in range(len(arr)-1,0,-1):
            if arr[i2]>= arr[i2-1]:
                continue
            else:
                break
        #arr[i2] - arr[len(arr)-1] is increasing and arr[i2-1] < arr[i2]
        print(i1,i2)
        remove = i2-1-(i1+1)+1
        ans = min(remove+i1+1,remove+len(arr)-i2)
        #binary search to find positions of num in first part in the second part
        for i in range(i1,-1,-1):
            num = arr[i]
            l,r = i2,len(arr)
            while l < r:
                mid = (l+r)//2
                if arr[mid] >= num:
                    r = mid
                else:
                    l = mid+1
            # if found
            if l < len(arr):
                cur = remove + i1-i + l- i2
                ans = min(cur,ans)
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        stack = [[len(arr)-1, arr[-1]]]
        
        for i in range(len(arr)-2, -1, -1):
            if arr[i] <= arr[i+1]:
                stack.append([i, arr[i]])
            else:
                break
        
        min_len = len(arr)-len(stack)
        
        for i in range(len(arr)):
            if i == 0 or arr[i] >= arr[i-1]:
                while len(stack) > 0 and (stack[-1][1] < arr[i] or stack[-1][0] <= i):
                    stack.pop()

                if len(stack) > 0:
                    min_len = min(min_len, stack[-1][0]-i-1)
                else:
                    min_len = min(min_len, len(arr)-i-1)
            else:
                break
        
        return min_len

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n=len(arr)
        answer=n-1
        
        A=arr
        if len(arr)==1:
            return 0
        flag=False
        for i in range(1,n):
            if A[i]<A[i-1]:
                flag=True
                j=n-1
                while(j>i and A[j]>=A[i-1]) and (j==n-1 or A[j]<=A[j+1]):
                    j=j-1
                answer=min(answer,j-i+1) 
                break
        if flag==False:
            return 0
       
        for i in range(n-2,-1,-1):
            if A[i]>A[i+1]:
                j=0
                while(j<i and A[j]<=A[i+1]) and (j==0 or A[j]>=A[j-1]):
                    j=j+1
                answer=min(answer,i-j+1)
                break
        return answer      


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if len(arr) < 2:
            return 0
        for i1 in range(len(arr)-1):
            if arr[i1+1] >= arr[i1]:
                continue
            else:
                break
        #arr[0] - arr[i1] is increasing and arr[i1+1] < arr[i1]
        #if overall sorted
        if arr[-2] <= arr[-1] and i1 == len(arr)-2:
            return 0
        for i2 in range(len(arr)-1,0,-1):
            if arr[i2]>= arr[i2-1]:
                continue
            else:
                break
        #arr[i2] - arr[len(arr)-1] is increasing and arr[i2-1] < arr[i2]
        # print(i1,i2)
        remove = i2-1-(i1+1)+1
        ans = min(remove+i1+1,remove+len(arr)-i2)
        #binary search to find positions of num in first part in the second part
        for i in range(i1,-1,-1):
            num = arr[i]
            l,r = i2,len(arr)
            while l < r:
                mid = (l+r)//2
                if arr[mid] >= num:
                    r = mid
                else:
                    l = mid+1
            # if found
            if l < len(arr):
                cur = remove + i1-i + l- i2
                ans = min(cur,ans)
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l = 0
        n = len(arr)
        while l<n-1 and arr[l]<=arr[l+1]:
            l+=1
        
        # print(l)
        if l == n-1:return 0
        # if l == 0: return len(arr)-1
        r = len(arr)-1
        while r>0 and arr[r]>=arr[r-1]:
            r-=1
        
        left = n-(l+1)
        right = r
        # print(r)
        ans = min(left,right)

        i=0
        j=r


        while i<=l and j<n:

            if arr[j]>=arr[i]:
                ans =min(ans,j-i-1)
                i+=1
            else:

                j+=1

        return ans


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l,r = 0,len(arr) - 1
        while l < r and arr[l + 1] >= arr[l]:
            l += 1
        if l == len(arr) - 1:
            return 0
        
        while r > 0 and arr[r - 1] <= arr[r]:
            r -= 1
        toRemove = min(len(arr) - l - 1,r)
        
        for iL in range(l + 1):
            if arr[iL] <= arr[r]:
                toRemove = min(toRemove,r - iL - 1)
            elif r < len(arr) - 1:
                r += 1
            else:
                break
        return toRemove

from sortedcontainers import SortedDict

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if len(arr) <= 1: return 0
        
        last = -float('inf')
        
        sl = SortedDict()
        
        for i, n in enumerate(arr):
            if n < last: break
            
            sl[n] = i
            
            last = n
                    
        ans = len(arr) - i
        last = float('inf')
        
        
        for i in range(len(arr)-1, 0, -1):
            if arr[i] > last: break
            
            last = arr[i]
            
            sl_idx = sl.bisect_right(arr[i])
                                    
            ans = min(ans, i - sl_idx)
        
        return max(0, ans)

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # check best from left
        # check best from right
        left, right = 0, len(arr) - 1
        while left < len(arr) - 1 and arr[left] <= arr[left + 1]:
            left += 1
        if left == len(arr) - 1:
             return 0
        while right > 0 and arr[right - 1] <= arr[right]:
            right -= 1
        best = min(len(arr) - 1 - left, right) # only prefix or suffix parts
        
        # merging prefix and suffix
        # first checking all elements smaller than left to see which ones can be used before the right index draw a line going from (0,0) -> (3,2) and a line going form (7, 1) -> (10, 3) and notice which arrays you can make by drawing horizontal lines on y = 1 and y = 2. 
        # Essentially we start from the beginning and we see which ones from the left can exist if right is where it was before. If we get to a left that is greater than right, we increment right by 1 to see if the next left < the next right. We keep on repeating this process until we cant (when the current left is greater than the current right and the current right is the last element). At that point, we just return the smallest we have seen until that time.
        for i in range(left + 1):
            if arr[i] <= arr[right]:
                best = min(best, right - i - 1)
            elif right < len(arr) - 1:
                right += 1
            else:
                break
        # The following method fails for [1,2,3,10,0,7,8,9]
        # for i in range(left + 1):
        #     if arr[i] <= arr[right]:
        #         best = min(best, right - i - 1)
        # for i in range(len(arr) - 1, right - 1, -1):
        #     print(arr[left], arr[i])
        #     if arr[left] <= arr[i]:
        #         best = min(best, i - left - 1)
        return best


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        k = 0
        while k+1 < len(arr) and arr[k+1] >= arr[k]:
            k += 1
        if k == len(arr) - 1:
            return 0
        l = len(arr) - 1
        while l > 0 and arr[l - 1] <= arr[l]:
            l -= 1
        ans = max(k + 1, len(arr) - l)
        for i in range(k + 1):
            while l < len(arr) and arr[i] > arr[l]:
                l += 1
            ans = max(ans, i + 1 + len(arr) - l)
        return len(arr) - ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l = len(arr)
        if l == 1:
            return 0
        
        longest = 0
        
        # three possibilities:
        # 1. head + tail, 2. head, 3. tail
            
        
        # head
        benchmark = 'a'
        
        for i in range(1, l):
            if arr[i-1] > arr[i]:
                head_longest = i
                benchmark = arr[i-1]
                break
        
        if benchmark == 'a':
            return 0
        
        i = l - 2
        if arr[i+1] >= benchmark:
            head_longest += 1
        while arr[i] <= arr[i+1] and arr[i] >= benchmark:
            head_longest += 1
            i -= 1
        
        
        # tail
        for i in range(l-2, -1, -1):
            if arr[i] > arr[i+1]:
                tail_longest = l - i - 1
                benchmark = arr[i+1]
                break
        
        i = 1
        if arr[i-1] <= benchmark:
            tail_longest += 1
            
        
        while arr[i-1] <= arr[i] and arr[i] <= benchmark:
            tail_longest += 1
            i += 1
            
        longest = max(head_longest, tail_longest)
        
        return l - longest

from bisect import bisect_left as bl ,bisect_right as br,bisect as bis,insort_left as il,insort_right as ir ,insort as isrt
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        
        maxarr=[1]
        n=len(arr)
        flag=0
        
        for i in range(1,n):
            if (arr[i]>=arr[i-1]):
                maxarr.append(maxarr[-1]+1)
            else:
                flag=1
                maxarr.append(1)
        if flag ==0:
            return 0
        arr1=[arr[0]]
        arr2=[arr[-1]]
        
        i=1
        while i<len(arr) and maxarr[i]>maxarr[i-1]:
            arr1.append(arr[i])
            i+=1
        
        i=len(arr)-2
        while i >=0 and maxarr[i]<maxarr[i+1]:
            arr2.append(arr[i])
            i-=1
        
        
        print((arr1, arr2[::-1]))
        arr2= arr2[::-1]
        size = len(arr2)
        maxm = len(arr1)
        for i in arr2:
            index = br(arr1 , i)
            maxm = max(index +size ,maxm)
            size-=1
     
            
            
                    
        
        
        return len(arr)-maxm
            
      
        
            
                
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # Find the longest monotonically non-decreasing prefix array in [0, i]
        n = len(arr)
        l = 1
        while l < n and arr[l-1] <= arr[l]:
            l += 1
        l -= 1  
        if l >= n - 2:
            return n - 1 - l
                
        # Find the longest monotonically non-decreasing suffix array in [j, n - 1]
        r = n - 2
        while r >= 0 and arr[r] <= arr[r+1]:
            r -= 1
        r += 1
        if r <= 1:
            return r
    
        # Start off with min of either left or right side removed as the min_to_move
        min_to_remove = min(n - 1, n - 1 - (l + 1) + 1, r)
        # Try to merge [0..i] from the left into [r..n-1]. We start with assuming
        # entire right side [r..n-1] could be included and try to see if [0], [0, 1] and so on
        # from the left side could be merged in. Until we hit some i on the left side that is 
        # too large for the current arr[r], retreat r back further to the right to try
        # against a bigger value. Keep trying until we run out of either room for i to expand
        # toward the right or for no more r left to retreat to the right.
        i = 0
        while i < l + 1:
            if arr[i] <= arr[r]:
                min_to_remove = min(min_to_remove, r - i - 1)
                # we could definitely include arr[i] into the result
                i += 1
            elif r < n - 1:
                # We cannot include arr[r] into the result but we could
                # include arr[i] into the result
                r += 1
                i += 1
            else:
                break
        
        return min_to_remove

        
    def findLengthOfShortestSubarray_bruteforce_bsearch(self, arr: List[int]) -> int:
        # Returns the smallest index `idx` such that arr[idx] >= val
        def bsearch(val, low, high):
            while low < high:
                mid = (low + high) // 2
                if arr[mid] >= val:
                    high = mid
                else:
                    low = mid + 1
            if val > arr[high]:
                return high + 1
            return high
        
        # Find the longest monotonically non-decreasing prefix array in [0, i]
        n = len(arr)
        curr_max = float('-inf')
        i = 0
        while i < n:
            if arr[i] < curr_max:
                break
            curr_max = arr[i]
            i += 1
        i -= 1  
        if i >= n - 2:
            return n - 1 - i
                
        # Find the longest monotonically non-decreasing suffix array in [j, n - 1]
        curr_min = float('inf')
        j = n - 1
        while j >= 0:
            if arr[j] > curr_min:
                break
            curr_min = arr[j]
            j -= 1
        j += 1
        if j <= 1:
            return j
        
        # For each value arr[k], in [0, i], find the `right_idx` into the suffix array in [j, n - 1]
        # such that arr[k] >= arr[right_idx]. We want to find the one that results in the longest
        # sequence [0..k] + [right_idx..n-1]
        min_to_remove = float('inf')
        for k in range(i, -1, -1):
            right_idx = bsearch(arr[k], j, n - 1)
            l = k + 1 + n - right_idx
            to_remove = n - l
            min_to_remove = min(min_to_remove, to_remove)
            
        # For each value arr[k], in [j, n-1], find the `left_idx` into the prefix array in [0, i]
        # such that arr[k] >= arr[left_idx - 1]. We want to find the one that results in the longest
        # sequence [0..left_idx-1] + [k..n-1]
        for k in range(j, n):
            left_idx = bsearch(arr[k], 0, i)
            l = left_idx + n - k
            to_remove = n - l
            min_to_remove = min(min_to_remove, to_remove)
        
        return min_to_remove
        
        

        
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        left, right = 0, n-1
        while left < n-1 and arr[left] <= arr[left+1]:
            #non-decreasing, keep increment
            left+=1
        while right>0 and arr[right] >= arr[right-1]:
            right-=1
        num_to_remove = min(n-left-1, right)
        
        #general case:
        #from the left
        for curr in range(left+1):
            if arr[curr]<=arr[right]:
                num_to_remove = min(num_to_remove, max(0, right-curr-1))
            else:
                # arr[curr]>arr[right]
                if right < n-1:
                    right += 1
                else:
                    #last element
                    break
        return num_to_remove
        


class Solution:

    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:

        # determine right sorted subarray
        r = len(arr) - 1 
        while r >0 and arr[r] >= arr[r-1]:
            r -= 1
           
        # determine left sorted subarray that can be merged with right
        ret = r # set ret to worst case, remove all left 
        l = 0
        for l in range(len(arr)):
            # if left subarry is not in order anymore, stop, can't do better
            if l>0 and arr[l] < arr[l-1]:
                break
            # if l==r
            if l == r:
                return 0
                
            while r < len(arr) and arr[l] > arr[r] :
                r +=1
            

            ret = min(ret, r-l-1)
                
            
            
        return ret
            

        

        

        
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        left, right = 1, 1
        
        
        i = 1
        while i < n and arr[i] >= arr[i - 1]:
            left += 1
            i += 1
        
        
        i = n - 2
        while i >= 0 and arr[i] <= arr[i + 1]:
            right += 1
            i -= 1
        
        
        l1, l2 = right, left
        
        i = n - right
        while i < n and arr[i] < arr[left - 1]:
            i += 1
            l1 -= 1
            
            
        i = left - 1
        while i >= 0 and arr[i] > arr[n - right]:
            i -= 1
            l2 -= 1
            
        return max(min(n - left - l1, n - right - l2), 0)

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l = []
        for x in arr:
            if not l or x >= l[-1]:
                l.append(x)
            else:
                break
        r = []
        for i in range(len(arr)-1, -1, -1):
            if not r or arr[i] <= r[-1]:
                r.append(arr[i])
            else:
                break
        r.reverse()
        if len(l) == len(arr):
            return 0
        sol = max(len(l), len(r))
        i, j = 0, 0
        # print(l, r)
        while i < len(l) and j < len(r):
            if l[i] <= r[j]:
                i += 1
            else:
                while j < len(r) and l[i] > r[j]:
                    j += 1
            # print(i, j)
            sol = max(sol, i+len(r)-j)
        return len(arr) - sol

class Solution:
    '''
    1,2,3,10,4,2,3,5]
    1 2 2  3 3 4 5 10
    '''
    def findLengthOfShortestSubarray(self, A: List[int]) -> int:
        N = len(A)
        left, right = 0, N - 1
        while left + 1 < N and A[left] <= A[left + 1]:
            left += 1
        if left == N - 1:
            return 0
        while right > left and A[right - 1] <= A[right]:
            right -= 1
        ans = min(N - left - 1, right)
        i, j = 0, right
        while i <= left and j < N:
            if A[j] >= A[i]:
                ans = min(ans, j - i - 1)
                i += 1
            else:
                j += 1
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        if(n==1):
            return 0
        l = 0 
        r = n - 1
        while(r > 0):
            if(arr[r-1] > arr[r]):
                break
            r = r - 1
        ans = r - l
        while(l < r):
            if(l > 0 and arr[l-1] > arr[l]):
                break
            while(r < n and arr[r] < arr[l]):
                r = r + 1
            ans = min(ans, r - l - 1)
            l = l + 1
        return ans


import bisect

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        a = 0
        for i in range(len(arr)):
            if i == 0 or arr[i] >= arr[i - 1]:
                a += 1
            else:
                break
        
        b = 0
        for i in reversed(list(range(len(arr)))):
            if i == len(arr) -1 or arr[i] <= arr[i + 1]:
                b += 1
            else:
                break
        
        if a == len(arr):
            return 0
        
        al = arr[: a]
        bl = arr[len(arr) - b: ]
        
        ans = len(arr) - 1
        
        for i in range(a):
            target = al[i]
            index = bisect.bisect_left(bl, target)
            if index == len(bl):
                ans = min(ans, len(arr) - i - 1)
            else:
                ans = min(ans, len(arr) - (i + 1) - (len(bl) - index))
        
        ans = min(ans, len(arr) - len(bl))
        
        return ans


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        arr = [-1e99]+arr+[1e99]
        
        
        left_p  = 0
        while left_p + 1 < len(arr) and arr[left_p] <= arr[left_p+1] :
            left_p += 1
        
        right_p = len(arr)-1
        while right_p-1 >= 0 and arr[right_p] >= arr[right_p-1] :
            right_p -= 1
        right_p_old = right_p
        if left_p > right_p :
            return 0
        
        while arr[right_p] < arr[left_p] :
            right_p += 1
        to_ret = right_p - left_p - 1
        
        while right_p >= right_p_old and left_p > 0 :
            left_p -= 1
            while right_p-1 >= right_p_old and arr[right_p-1] >= arr[left_p] :
                right_p -= 1
            to_ret = min(to_ret, right_p - left_p - 1 )
        
        return to_ret
        
        
        # 10 2 99 12 13


class Solution:
    # O(n)
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:

        # determine right sorted subarray
        r = len(arr) - 1 
        while r >0 and arr[r] >= arr[r-1]:
            r -= 1
        
        # r == 0 means array is sorted
        if r == 0:
            return 0
        
        # now determine left sorted subarray that can be merged with right
        ret = r # set ret to worst case, remove all left 
        l = 0
        for l in range(len(arr)):
            # if left subarry is not in order anymore, stop, can't do better
            if l>0 and arr[l] < arr[l-1]:
                break
            
            # if arr[l] is larger than the left edge of right sorted subarray, 
            # push the edge to the right
            # why this work? Is it OK to push to the right? We won't consider
            # arr[i+1] and arr[r].
            # It's OK! We don't have to consider arr[i+1] and arr[r].
            # if arr[i] is larger than the left edge, arr[i+1] is larger too!
            # so it won't be the possible answer
            # it's possible that you push it to the end of right subarray
            # for example [9,10,11,5], keep pushing r to 4
            # in this case, right subarray is empty [].
            while r < len(arr) and arr[l] > arr[r] : 
                r +=1 

            ret = min(ret, r-l-1)

        return ret
            

        

        

        
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        N = len(arr)
        
        lo, hi = 0, N - 1
        while lo + 1 < N and arr[lo] <= arr[lo + 1]:
            lo += 1
        if lo >= N - 1:
            return 0
        
        while hi - 1 >= 0 and arr[hi - 1] <= arr[hi]:
            hi -= 1
            
        # [0..lo]    [hi..N-1]
        res = min(N - lo - 1, hi)
        j = hi
        for i in range(lo + 1):
            while j < N and arr[j] < arr[i]:
                j += 1
            res = min(res, j - i - 1)
        return res

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l = res =  0
        r = n = len(arr)
        increasing = [0] * n 
        
        for i in range(1, n):
            if arr[i] >= arr[i-1]:
                increasing[i] = 1 + increasing[i-1]
        # print(arr) 
        # print(increasing)
        while l < r:
            mid = (l+r) // 2
            # print(mid)
            for i in range(n - mid + 1):
                isLeftInc = False
                isRightInc = False
                if i > 0 and increasing[i-1] == i-1 or i == 0:
                    isLeftInc = True

                if (i < n-mid and increasing[n-1] >= n - i - mid - 1 and arr[i+mid] >= (0 if i < 1 else arr[i-1])) or i == n-mid :
                    isRightInc = True
                # print(i, isLeftInc, isRightInc, i + mid, i-1)       

                if isLeftInc and isRightInc:
                    break
                    
            if isLeftInc and isRightInc:
                res = mid
                r = mid
            else:
                l = mid+1
                    
        return res

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        i=0
        while i<len(arr)-1 and arr[i]<=arr[i+1]:
            i+=1
        if i==len(arr):return 0
        j=len(arr)-1
        
        while j and arr[j-1]<=arr[j]:
            j-=1
        if j==-1:return 0
                
        def lowerbound(left, right, target):
            while left < right:
                mid = left + (right - left) // 2
                
                if arr[mid] == target:
                    right = mid
                elif arr[mid] < target:
                    left = mid + 1
                else:
                    right = mid
                
            return left            
        N=len(arr)
        print((i,j))
        out=min(N - (N - j), N - i -1)
        print(out)
        for k in range(i+1):
            hi=lowerbound(j,len(arr),arr[k])
            out=min(out,hi-k-1)
        
        return max(0,out)
            
        
        
        
        
        
            
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        p = 1
        while p < len(arr) and arr[p] >= arr[p - 1]:
            p += 1
        first = p
        p = len(arr) - 1
        while p >= 1 and arr[p] >= arr[p - 1]:
            p -= 1
        second = p
        ans = min(len(arr) - first, second)
        i, j = 0, second
        # print(i, j)
        while i < first and j < len(arr):
            if arr[i] > arr[j]:
                ans = min(ans, j - i)
                j += 1
            else:
                i += 1
        ans = min(ans, j - i)
        return ans if ans > 0 else 0

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if len(arr) <= 1:
            return 0
        
        p1 = 0
        p2 = len(arr) - 1
        
        for i in range(1,len(arr)):
            if arr[i] >= arr[i-1]:
                p1 += 1
            else:
                break
        
        for i in range(len(arr)-2, -1, -1):
            if arr[i] <= arr[i+1]:
                p2 = i
            else:
                break
        ans = min(len(arr) - p1 - 1 , p2)
        if p1 > p2:
             return ans
        p11, p22 = 0, p2
        
        while p11 <= p1 and p22 < len(arr):
            if arr[p11] <= arr[p22]:
                ans = min(ans, p22 - p11 - 1)
                p11 += 1
            else:
                p22 += 1
        return ans

from functools import lru_cache

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        '''
        1 2 3 10 4 2 3 5
            i
                     j
                       
        1  2 3
          ij
        '''
        N = len(arr)
        i = 0
        while i < N-1 and arr[i+1] >= arr[i]:
            i += 1
        left = N - i - 1
        
        j = N-1
        while j > 0 and arr[j-1] <= arr[j]:
            j -= 1
        right = j
        
        ret = N-1
        
        @lru_cache(maxsize=None)
        def search(i, j):
            print(i, j)
            nonlocal ret
            if i == j: return 0

            if arr[j] >= arr[i]:
                ret = min(ret, j-i-1)
            
            I = i
            while i < N-1 and arr[i+1] >= arr[i] and arr[i+1] <= arr[j]:
                i += 1
            if i > I:
                search(i, j)
            
            i = I
            J = j
            while j > 0 and arr[j-1] <= arr[j] and arr[j-1] >= arr[i]:
                j -= 1
            if j < J:
                search(i, j)
                    
        search(0, N-1)
        
        return min(left, ret, right)

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        lastPos = len(arr)-1
        stop = False
        idx = len(arr)-2
        while idx > -1 and not stop:
            num = arr[idx]
            prev = arr[lastPos]
            if num <= prev:
                lastPos = idx
            else:
                stop = True
            idx -= 1
        rightSub = lastPos
        
        minSub = rightSub
        idx = 0
        stop = False
        valid = False
        while idx < rightSub and not stop:
            valid = False
            if idx == 0 or arr[idx] >= arr[idx-1]:
                num = arr[idx]
                while rightSub < len(arr) and not valid:
                    numRight = arr[rightSub]
                    if numRight < num:
                        rightSub += 1
                    else:
                        valid = True
                minSub = min(minSub, (rightSub - idx - 1))        
                idx += 1
            else:
                stop = True
            
        idx -= 1
        minSub = min(minSub, (rightSub - idx - 1))
        return minSub
        
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        ans = float('inf')
        max_s, min_e = 0, n-1
        curr = -1
        for i, a in enumerate(arr):
            if a < curr: break
            curr = a
            max_s = i
        
        curr = float('inf')
        for i in range(n-1, -1, -1):
            if arr[i] > curr: break
            curr = arr[i]
            min_e = i
        # n - 1 - (max_s + 1) + 1 = n - 1 - max_ s
        # min_e - 1 - 0 + 1 = min_e
        ans = min(n - max_s - 1, min_e)
        
        for s in range(max_s+1):
            index, jump = n-1, n - 1 - min_e
            while jump >= 1:
                while index-jump >= min_e and arr[index-jump] >= arr[s]:
                    index -= jump
                jump //= 2
            if arr[index] >= arr[s]:
                ans = min(ans, index-1 - (s + 1) + 1)
        return max(ans, 0)
            


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if arr == sorted(arr):
            return 0
        for head in range(len(arr) - 1):
            if arr[head] > arr[head + 1]:
                break
        if head == len(arr):
            return 0 # already sorted
        for tail in range(len(arr) - 1, 0, -1):
            if arr[tail - 1] > arr[tail]:
                break
        lo = head + 1
        hi = len(arr)
        output = float('inf')
        while lo >= 0:
            while hi - 1 >= tail and (lo == 0 or arr[lo - 1] <= arr[hi - 1]):
                hi -= 1
            output = min(output, hi - lo)
            lo -= 1
        return output

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        ans = float('inf')
        max_s, min_e = 0, n-1
        curr = -1
        for i, a in enumerate(arr):
            if a < curr: break
            curr = a
            max_s = i
        
        curr = float('inf')
        for i in range(n-1, -1, -1):
            if arr[i] > curr: break
            curr = arr[i]
            min_e = i
        # n - 1 - (max_s + 1) + 1 = n - 1 - max_ s
        # min_e - 1 - 0 + 1 = min_e
        ans = min(n - max_s - 1, min_e)
        
        for s in range(max_s+1):
            index, jump = n-1, n-1
            while jump >= 1:
                while index-jump >= min_e and arr[index-jump] >= arr[s]:
                    index -= jump
                jump //= 2
            if index > s and arr[index] >= arr[s]:
                ans = min(ans, index-1 - (s + 1) + 1)
        return ans
            


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        def bsearch(val, low, high):
            while low < high:
                mid = (low + high) // 2
                if arr[mid] >= val:
                    high = mid
                else:
                    low = mid + 1
            if val > arr[high]:
                return high + 1
            return high
        
        n = len(arr)
        curr_max = float('-inf')
        i = 0
        while i < n:
            if arr[i] < curr_max:
                break
            curr_max = arr[i]
            i += 1
        i -= 1  
        if i >= n - 2:
            return n - 1 - i
                
        curr_min = float('inf')
        j = n - 1
        while j >= 0:
            if arr[j] > curr_min:
                break
            curr_min = arr[j]
            j -= 1
        j += 1
        if j <= 1:
            return j
        
        min_to_remove = float('inf')
        for k in range(i, -1, -1):
            right_idx = bsearch(arr[k], j, n - 1)
            l = k + 1 + n - right_idx
            to_remove = n - l
            min_to_remove = min(min_to_remove, to_remove)
        for k in range(j, n):
            left_idx = bsearch(arr[k], 0, i)
            l = left_idx + n - k
            to_remove = n - l
            min_to_remove = min(min_to_remove, to_remove)
        
        return min_to_remove
        
        

        
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if arr == None or len(arr) <= 1:
            return 0
        left ,right = 0, len(arr) - 1
        while left +1 < len(arr) and arr[left] <= arr[left+1] : left += 1
        if left == len(arr)-1: return 0
        while right > 0 and arr[right-1] <= arr[right] : right -= 1
        result = min(len(arr)-left-1, right)
        if arr[left] <= arr[right]:
            result = min(result, right-left-1)
        for i in range(left+1):
            if arr[i] <= arr[right] : result = min(result, right-i-1)
            elif right < len(arr)-1 : right += 1
        return result

class Solution:
    def canBeMadeSortedByDeletingKElements(self, arr: List[int], k: int) -> bool:
        # k   : 0 1 2 3 4 5 . . . 
        # f(k): 0 0 0 0 1 1 1 1 1 1 1 1
        n = len(arr)
        
        i = 1
        while i < n and arr[i - 1] <= arr[i]:
            i += 1
            
        j = 1
        while j < n and arr[n - j - 1] <= arr[n - j]:
            j += 1
        
        if i == n: # and j == n
            return True
            
        # i         > k         j
        # -----  # # # # # ------
        # 3 4 5 1 1 2 3 4
        # k = 2
            
        if i + j + k < n:
            return False
        
        # k = 3
        # 0 1 2 3 4 5 6
        
        # k = 3
        #        0 1 2 3 4 5
        # i = 0: - - -
        # i = 1:   - - - 
        
        for start in range(0, n - k + 1):
            left = start
            right = n - left - k
            if left <= i and right <= j and (left == 0 or right == 0 or arr[left - 1] <= arr[n - right]):
                return True
        
        return False
    
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        L = 0
        R = len(arr) - 1
        answer = -1
        
        while L <= R:
            M = (L + R) // 2
            if self.canBeMadeSortedByDeletingKElements(arr, M):
                answer = M
                R = M - 1
            else:
                L = M + 1
        
        return answer


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l = 0
        r = len(arr)-1
        while l < len(arr)-1 and arr[l+1] >= arr[l]:
            l +=1
        if l == len(arr)-1:
            return 0
        while r > 0 and arr[r-1] <= arr[r]:
            r -=1
        
        res = min(len(arr)-l-1, r)
        
        for i in range(l+1):
            if arr[i] <= arr[r]:
                res = min(res, r-i-1)
            elif r < len(arr)-1:
                r +=1
            else:
                break
                
        return res


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if all([arr[i+1] >= arr[i] for i in range(len(arr)-1)]):
            return 0
        start = 0
        for i in range(1, len(arr)):
            if arr[i] >= arr[i-1]:
                start = i
            else:
                break
        end = len(arr) - 1
        for i in range(len(arr)-1)[::-1]:
            if arr[i] <= arr[i+1]:
                end = i
            else:
                break
        lo = -1
        res = min(len(arr) - start - 1, end)
        for i in range(end, len(arr)):
            while lo < start and arr[lo+1] <= arr[i]:
                lo += 1
            res = min(res, i - lo - 1)
        return res

import bisect
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        s={}
        a=[(arr[0],0)]
        s[0]=(0,0)
        n=len(arr)
        for i in range(1,n):
            if s[i-1][1]==0:
                move=1
            else:
                move=s[i-1][0]+1
            index=bisect.bisect_right(a,(arr[i],i))
            if index==0:
                nmove=i
            else:
                nmove=i-a[index-1][1]-1
            if arr[i-1]<=arr[i]:
                nmove=min(nmove,s[i-1][1])
            if nmove==0:
                bisect.insort_right(a,(arr[i],i))
            s[i]=(move,nmove)
            #print(s)
        return min(s[n-1][0],s[n-1][1])
            
            
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        left = 0
        while left < len(arr) - 1:
            if arr[left] <= arr[left + 1]:
                left += 1
            else:
                break
        if left >= len(arr) - 1:
            return 0
        right = len(arr) - 1
        while right > 0:
            if arr[right] >= arr[right - 1]:
                right -= 1
            else:
                break
        ll = 0
        rr = right
        res = min(len(arr) - left - 1, right)
        while ll < left + 1 and rr < len(arr):
            if arr[ll] <= arr[rr]:
                res = min(res, rr - ll - 1)
                ll += 1
            else:
                rr += 1
        return res
                
            
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)

        left = [False] * n # all to left are  increasing
        right = [False] * n # all to right are  increasing
        
        left[0] = True
        right[n-1] = True
        for i in range(1, n):
            left[i] = left[i - 1] and (arr[i] >= arr[i-1])
            
        for i in range(n-2, -1, -1):
            right[i] = right[i + 1] and (arr[i] <= arr[i + 1])
            
            
        
        def isPossible(num):
            res = False
            for i in range(n):
                if i == 0 or left[i - 1]:
                    if i + num >= n or (right[i + num] and (i == 0 or arr[i - 1] <= arr[i + num])):
                        res = True
                        break                    
            return res
            
        be = 0
        en = n - 1
        
        while be < en:
            mid = be + (en - be) // 2
            if isPossible(mid):
                en = mid
            else:
                be = mid + 1
        
        return be
    


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        right=[]
        left=[]
        if not arr:
            return 0
        pre=arr[-1]+1
        while arr and arr[-1]<=pre:
            pre=arr[-1]
            right.append(arr.pop())
        pre=-1
        while arr and arr[0]>=pre:
            pre=arr[0]
            left.append(arr.pop(0))
        l=[i for i in left]
        r=[i for i in right]
        val=0
        while l and r and l[-1]>r[-1]:
            l.pop()
            val+=1
        out=val
        val=0
        while right and left and right[-1]<left[-1]:
            right.pop()
            val+=1
        out=min(out,val)
        return out+len(arr)

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l, r = 0, len(arr) - 1
        while l < r and arr[l+1] >= arr[l]:
            l += 1
        if l == len(arr) - 1:
            return 0 # whole array is sorted
        while r > 0 and arr[r-1] <= arr[r]:
            r -= 1
            
        toRemove = min(len(arr) - l - 1, r)
        for iL in range(l+1):
            if arr[iL] <= arr[r]:
                toRemove = min(toRemove, r - iL - 1)
            elif r < len(arr) - 1:
                r += 1
            else:
                break
        
        return toRemove

class Solution:
    def findLengthOfShortestSubarray(self, nums: List[int]) -> int:
        # equal to max increasing subarray 
        seqs = [0]
        last = nums[0]
        
        for i, num in enumerate(nums[1:]):
            if num < last:
                seqs.append(i+1)
            last = num
        if len(seqs) == 1:
            return 0
        
        no_first_size = seqs[-1]
        has_first_size = len(nums) - seqs[1]
        for first_end in range(0, seqs[1]):
            first_size = len(nums)
            for i in range(seqs[-1], len(nums)):
                if nums[i] >= nums[first_end]:
                    first_size = i - first_end - 1
                    break
            has_first_size = min(has_first_size, first_size)
            if first_size == len(nums):
                break
        return min(no_first_size, has_first_size)
                


class Solution(object):
    def findLengthOfShortestSubarray(self, arr):
        stack = [[len(arr)-1, arr[-1]]]
        
        for i in range(len(arr)-2, -1, -1):
            if arr[i] <= arr[i+1]:
                stack.append([i, arr[i]])
            else:
                break
        
        min_len = len(arr)-len(stack)
        
        for i in range(len(arr)):
            if i == 0 or arr[i] >= arr[i-1]:
                while len(stack) > 0 and (stack[-1][1] < arr[i] or stack[-1][0] <= i):
                    stack.pop()

                if len(stack) > 0:
                    min_len = min(min_len, stack[-1][0]-i-1)
                else:
                    min_len = min(min_len, len(arr)-i-1)
            else:
                break
        
        return min_len

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        
        before = n
        after = 0
        for i in range(1, n):
            if arr[i] < arr[i - 1]:
                before = i - 1
                break
        if before == n:
            return 0
        for i in range(n - 1)[::-1]:
            if arr[i] > arr[i + 1]:
                after = i + 1
                break
        l, r = 0, n
        while l < r:
            m = l + (r - l) // 2
            ok = before >= n - 1 - m or after <= m

            for start in range(1, n):
                if start + m >= n:
                    break
                else:
                    left = before >= start - 1
                    right = after <= start + m
                    ok |= left and right and arr[start - 1] <= arr[start + m]
            if ok:
                r = m
            else:
                l = m + 1
        return l 

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1: return 0
        last = n - 1
        while last > 0 and arr[last - 1] <= arr[last]: last -= 1
        ans = last
        
        for i in range(n):
            if i > 0 and arr[i] < arr[i - 1]: break
            while last < n and (last <= i or arr[last] < arr[i]): last += 1
            ans = min(ans, last - i - 1)
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, A: List[int]) -> int:
        N = len(A)
        if N == 1: return 0
        
        # Find left_end and right start
        left_end, right_start = 0, N - 1
        for i in range(1, N):
            if A[i] >= A[i-1]:
                left_end = i
            else:
                break
        
        for i in range(N-2, -1, -1):
            if A[i] <= A[i+1]:
                right_start = i
            else:
                break
                
        # Increasing array, no need to do anything
        print((left_end, right_start))
        if left_end > right_start: return 0
        ret = min(N - left_end - 1, right_start)
        
        # Two pointer
        j = right_start
        for i in range(left_end + 1):
            if j < N and A[i] <= A[j]:
                ret = min(ret, j - i - 1)
            else:
                while j < N and A[j] < A[i]:
                    j += 1
                ret = min(ret, j - i - 1)
        
        return ret


from bisect import bisect_right
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        for i in range(len(arr)-1):
            if arr[i+1]<arr[i]:
                u = i
                break
        else:
            return 0
        
        for j in range(len(arr)-1,-1, -1):
            if arr[j]<arr[j-1]:
                v = j
                break
        
        arr1 = arr[:u+1]
        arr2 = arr[v:]
        print(arr1, arr2)
        ans = len(arr)
        for i in range(len(arr2)):
            ans = min(ans, len(arr) - (bisect_right(arr1, arr2[i]) + 1 + len(arr2)-i-1))
        return min(ans, len(arr)-len(arr1), len(arr)-len(arr2))

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        def helper(i, j):
            if i < 0 or j >= len(arr):
                return 0
            if arr[i] > arr[j]:
                return min(helper(i-1, j), helper(i, j+1)) + 1
            return 0
        intervals = []
        start = 0
        end = 1
        while end < len(arr):
            if arr[end] >= arr[end-1]:
                end += 1
            else:
                intervals.append((start, end))
                start = end
                end = start + 1
                
        if start != len(arr):
            intervals.append((start, end))
        
        if len(intervals) < 2:
            return 0
        result = intervals[-1][0] - intervals[0][1]
        return result + helper(intervals[0][1]-1, intervals[-1][0])

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if arr == list(sorted(arr)):
            return 0
        increasing_parts = []
        curr = []
        for num in arr:
            if not curr or curr[-1] <= num:
                curr.append(num)
            else:
                increasing_parts.append(curr)
                curr = [num]
        increasing_parts.append(curr)
        first = set(increasing_parts[0])
        second = set(increasing_parts[-1])
        first_pos = {}
        sec_pos = {}
        last_start = sum([len(x) for x in increasing_parts[:-1]])
        
        for i, num in enumerate(increasing_parts[0]):
            first_pos[num] = i
        
        for i, num in enumerate(increasing_parts[-1]):
            sec_pos[num] = i + last_start
        
        best = 0
        seq = list(sorted(increasing_parts[0] + increasing_parts[-1]))
        for i, num in enumerate(seq):
            if num in first:
                if i < len(seq) - 1 and seq[i + 1] in second:
                    best = max(first_pos[num] + 1 + len(arr) - sec_pos[seq[i + 1]], best)
        return min([len(arr) - len(increasing_parts[0]), len(arr) - len(increasing_parts[-1]), len(arr) - best])

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        L1=[arr[0]]
        L2=[]

        for i in range(1,len(arr)):
            if arr[i]>=arr[i-1]:
                L1.append(arr[i])
            else:
                break
        temp=[arr[-1]]
        for i in range(len(arr)-2,-1,-1):
            if arr[i]<=arr[i+1]:
                temp.append(arr[i])
            else:
                break
        L2=temp[-1::-1]
        
        margin=len(arr)-(len(L1)+len(L2))
        m=min(len(L1),len(L2))

        MIN=m+margin
        LENGTH1=len(L1)-1
        LENGTH2=len(L2)-1
        # print(L1,L2)
        

        i=len(L1)-1
        j=len(L2)-1

        while i>=0 and j>=0:
            if L1[i]<=L2[j]:
                j-=1

                a=LENGTH1-i
                b=j+1
                # print(i,j,a+b)
                MIN=min(MIN,margin+a+b)

            else:
                i-=1
                if j!=LENGTH2:
                    j+=1
                # print(i,j)
        # print()
        i=0
        j=0
        while i<len(L1) and j<len(L2):
            if L1[i]<=L2[j]:
                i+=1
                a=LENGTH1-i+1
                b=j
                # print(i,j,a+b)
                MIN=min(MIN,margin+a+b)

            else:
                j+=1
                if i!=0:
                    i-=1
                # print(i,j)
        
        
        if MIN<0:
            MIN=0
        return MIN

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        left = [float('inf') for _ in range(len(arr))]
        right = [-float('inf') for _ in range(len(arr))]
        
        last = -float('inf')
        for i,x in enumerate(arr):
            if x >= last:
                left[i] = x
            else:
                break
            last = x
        last = float('inf')
        _n = len(arr) - 1
        right_k = 0
        for i,x in enumerate(reversed(arr)):
            if x <= last:
                right[_n-i] = x
            else:
                right_k = i
                break
            last = x
            
        ans = float('inf')
        import bisect
        for i,x in enumerate(left):
            if x < float('inf'):
                j = bisect.bisect_left(right, x, i+1)
                ans = min(ans, j-i-1)
            else:
                break
        ans = min(ans, len(arr)-right_k)
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        a = [float('-inf')] + arr + [float('inf')]
        n = len(a)
        nondecrleft = [0] * n
        nondecrleft[0] = 1
        for  i in range(1, n):
            if a[i] < a[i-1]:
                break
            nondecrleft[i] = 1    
        
        
        nondecrright = [0] * n
        nondecrright[n-1] = 1
        for i in range(n-2, -1, -1):
            if a[i] > a[i+1]:
                break
            nondecrright[i] = 1    
                
                
        def f(l):
            # true if removing l elements can make arr sorted
            for i in range(1, n - l):
                if nondecrleft[i-1] and nondecrright[i+l] and a[i-1] <= a[i+l]:
                    return True
            return False    
        lo, hi = 0, n-2  
        while lo!= hi:
            p = (lo + hi) // 2
            if not f(p):
                lo = p + 1
            else:
                hi = p
        return lo    


from collections import deque
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n=len(arr)
        arr.append(-1)
        decrease=[]
        for i in range(n-1):
            if arr[i]>arr[i+1]:
                decrease.append(i)
        if len(decrease)==0:
            return 0
        start=decrease[0]+1
        end=decrease[-1]
        def valid(start,end):
            if arr[start-1]<=arr[end+1]:
                return True
            return False
        res=n-1
        for i in range(start,-1,-1):
            lo,hi=end,n-1
            while lo<=hi:
                mid=(lo+hi)//2
                if valid(i,mid): #hi+1 is valid
                    hi=mid-1
                else:#lo-1 is not valid
                    lo=mid+1
            lo=min(lo,n-1)
            # print(start,lo,i,lo-i+1)
            res=min(res,lo-i+1)
        return res
            
                    
            
            


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if not arr: return 0
        arr = [-10000000] + arr
        i = 0
        for j in range(i+1, len(arr)):
            if arr[j] >= arr[i]:
                i += 1
            else:
                break
        
        firsti = i
        
        j = len(arr)-1
        for i in range(j-1, -1, -1):
            if arr[j] >= arr[i]:
                j -=1
            else:
                break
        lastj = j
        
        n = len(arr)
        res = n-1
        for i1 in range(firsti+1):
            while lastj < n and arr[lastj] < arr[i1]: lastj += 1
            print((i1, lastj))
            res = min(res, lastj - i1 - 1)
        
        return max(res, 0)


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        l, r = 0, n-1
        # left
        for i in range(1, n):
            if arr[i] >= arr[i-1]:
                l += 1
            else:   break
        
        # if l == n-1:    return 0
        # right
        for i in reversed(list(range(1, n))):
            if arr[i] >= arr[i-1]:
                r -= 1
            else:   break
        
        # left find right
        res = min(n-l, r)
        for i in reversed(list(range(1, l+1))):
            j = self.bsearch(arr, arr[i], r, n-1)
            if arr[j] < arr[i]:
                res = min(res, j-i)
            else:
                res = min(res, j-i-1)
            
        # right find left
        # [1,2,3,10,4,2,3,5]
        for i in range(r, n):
            j = self.bsearch(arr, arr[i], 0, l)
            if arr[j] > arr[i]:
                res = min(res, i-j)
            else:
                res = min(res, i-j-1)
                
        return max(0, res)
    
    def bsearch(self, A, target, s, e):
        while s < e:
            m = s + (e-s)//2
            if A[m] < target:
                s = m+1
            else:
                e = m
        return e
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        pointer1=-1
        n=len(arr)
        pointer2=n-1
        for i in range(n-2,0,-1):
            if  arr[i]>arr[i+1]:
                break
            pointer2=i
        res=pointer2-pointer1-1
        for pointer1 in range(n):
            if pointer1>0 and arr[pointer1]<arr[pointer1-1]:
                break
            while(pointer2<n and (pointer2<=pointer1 or arr[pointer2]<arr[pointer1])):
                pointer2+=1
            res=min(res,pointer2-pointer1-1)
        return res


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        
        leftIncreasing, rightDecreasing = 1, 1
        
        for left, right in zip(arr, arr[1:]):
            if left <= right: leftIncreasing += 1
            else: break
        
        for right, left in zip(arr[::-1], arr[::-1][1:]):            
            if left <= right: rightDecreasing += 1
            else: break
        
        if max(leftIncreasing, rightDecreasing) == len(arr):
            return 0
        
        else:
            left_candidate, right_candidate = 0, len(arr) - rightDecreasing
            max_crop_length = max(leftIncreasing, rightDecreasing)
            
            if max_crop_length == leftIncreasing: crop_start, crop_end = leftIncreasing, len(arr) - 1
            else: crop_start, crop_end = 0, len(arr) - rightDecreasing - 1
            
            while left_candidate < leftIncreasing and right_candidate < len(arr):
                # print(left_candidate, leftIncreasing, right_candidate, rightDecreasing, crop_start, crop_end)
                if arr[left_candidate] > arr[right_candidate]:
                    while right_candidate < len(arr):
                        if arr[left_candidate] > arr[right_candidate]:
                            right_candidate += 1
                        else:
                            break
                    if right_candidate == len(arr):
                        return len(arr[crop_start: crop_end + 1])
                    else:
                        if max_crop_length < (left_candidate + 1) + (len(arr) - right_candidate):
                            crop_start, crop_end = left_candidate + 1, right_candidate - 1
                            max_crop_length = (left_candidate + 1) + (len(arr) - right_candidate)
                else:
                    if max_crop_length < (left_candidate + 1) + (len(arr) - right_candidate):
                        crop_start, crop_end = left_candidate + 1, right_candidate - 1
                        max_crop_length = (left_candidate + 1) + (len(arr) - right_candidate)
                    left_candidate += 1
                    
            return len(arr[crop_start: crop_end + 1])
            
                
                
                


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        i,j = -1,-1
        L = len(arr)
        for k in range(L-1):
            if arr[k]>arr[k+1]:
                j = k+1
                if i==-1:
                    i = k
        #print(i,j)
        if i==-1:
            return 0
        res = j
        for m in range(i+1):
            while j<=L-1:
                if arr[j]>=arr[m]:
                    break
                j += 1
            if j==L:
                return min(res,L-i-1)
            else:
                res = min(res,j-m-1)
            #print(m,j,res)
        return res

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        queue = deque([arr[-1]])
        for i in range(len(arr)-1, 0, -1):
            if arr[i-1] > arr[i]:
                break
            queue.appendleft(arr[i-1])
            
        if len(queue) == len(arr):
            return 0
        
        l = len(arr) - len(queue)
        def search(target):
            lo = l
            hi = l+len(queue)
            
            while lo < hi:
                mid = (lo + hi) // 2
                if arr[mid] >= target:
                    hi = mid
                else:
                    lo = mid+1
            return lo
        
        curMin = len(arr) - len(queue)
        i = 0
        while i < len(arr)-1 and arr[i] <= arr[i+1]:
            idx = search(arr[i])
            curMin = min(idx-i-1, curMin)
            i += 1
        idx = search(arr[i])
        curMin = min(idx-i-1, curMin)
        
        return curMin


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n, l = len(arr), 0 
        
        while l+1 < n and arr[l+1] >= arr[l]: 
            l += 1  
            
        if l == n-1: 
            return 0   
        
        r = n-1
        
        while r > 0 and arr[r-1] <= arr[r]: 
            r -= 1          
            
        if arr[l] <= arr[r]: 
            return r-l-1
        
        ans = min(n-l-1, r)
        
        for i in range(l+1): 
            if arr[i] <= arr[r]: 
                ans = min(ans, r-i-1)               
            elif r < n-1: 
                r += 1

        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l,r = 0,len(arr) - 1
        while l < r and arr[l + 1] >= arr[l]:
            l += 1
            
        if l == len(arr) - 1:
            return 0
            
        while r < len(arr) and arr[r - 1] <= arr[r]:
            r -= 1
            
        toRemove = min(len(arr) - l - 1,r)
        
        for iL in range(l + 1):
            if arr[iL] <= arr[r]:
                toRemove = min(toRemove,r - iL - 1)
            elif r < len(arr) - 1:
                r += 1
            else:
                break
        return toRemove

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        if n < 2: return 0
        left, right = 1, n - 1
        while left < n and arr[left] >= arr[left - 1]:
            left += 1
        if left == n:
            return 0
        while left < right and arr[right] >= arr[right - 1]:
            right -= 1
        res = min(n - left, right)
        left -= 1
        while left >= 0:
            l, r = right - 1, n - 1 # l < arr[m] <= r
            while r - l > 1:
                m = (l + r) // 2
                if arr[m] >= arr[left]:
                    r = m
                else:
                    l = m
            if arr[left] > arr[r]: r += 1
            res = min(res, r - left - 1)
            left -= 1
        return res
            
        
        
        
        
        
        
# 5 1 2 3 4
# 1 2 3 4 1

# 1 2 3 4 5 100 2 3 4 5 4 7 8 10 3 4 5 6 7 8
#               l                r


# 10 11 12 5 6 7 8 9 10 11 12 1 2 3 4


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        res = 0
        if len(arr) > 1:
            mr = len(arr)-1
            while mr - 1 >= 0 and arr[mr - 1] <= arr[mr]:
                mr -= 1
            if mr > 0:
                cr, res = mr, mr
                prev = -1
                for ml in range(0, len(arr)):
                    if prev <= arr[ml]:
                        while mr < len(arr) and arr[ml] > arr[mr]:
                            mr += 1
                            cr += 1
                        cr -= 1
                        res = min(res, cr)
                    else:
                        break
                    prev = arr[ml]
                
                
        return res

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        left, right = n-1, 0
        for i in range(n):
            if i > 0 and arr[i] < arr[i-1]:
                left = i-1
                break
        for i in range(n-1, -1, -1):
            if i < n-1 and arr[i] > arr[i+1]:
                right = i+1
                break
        if left >= right:
            return 0
        
        ans = min(n-left, right)
        j = right
        for i in range(left+1):
            if j < len(arr) and arr[j] < arr[i]:
                j += 1
            ans = min(ans, j-i-1)
        return ans


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        peak=0
        while peak<len(arr)-1 and  arr[peak]<=arr[peak+1]:
            peak+=1
        if peak==len(arr)-1:
            return 0
        valley=len(arr)-1
        while valley>0 and  arr[valley]>=arr[valley-1]:
            valley=valley-1
        ans=min(valley,len(arr)-peak-1)
        i=0
        j=valley
        while i<=peak and j<len(arr):
            if arr[j]>=arr[i]:
                ans=min(ans,j-i-1)
                i+=1
            else:
                j+=1
        return ans
        
            
                
                


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n=len(arr)
        i=0
        for i in range(n-1):
            if arr[i+1]<arr[i]:
                break
        left=i
        for i in range(n-1,0,-1):
            if arr[i-1]>arr[i]:
                break
        right=i
        if right<=left:
            return 0
        i=0
        j=right
        ans=min(n-left-1,right)
        while i<=left and j<n:
            if arr[i]<=arr[j]:
                ans=min(ans,j-i-1)
                i+=1
            elif arr[j]<arr[i]:
                j+=1
        return n-1 if ans==n+1 else ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        stack = [(len(arr)-1, arr[-1])]
        
        for i in range(len(arr)-2, -1, -1):
            if arr[i] <= arr[i+1]:
                stack.append([i, arr[i]])
            else:
                break
        
        min_len = len(arr)-len(stack)
        
        for i in range(len(arr)):
            if i == 0 or arr[i] >= arr[i-1]:
                while len(stack) > 0 and (stack[-1][1] < arr[i] or stack[-1][0] == i):
                    stack.pop()

                if len(stack) > 0:
                    min_len = min(min_len, stack[-1][0]-i-1)
                else:
                    min_len = min(min_len, len(arr)-i-1)
            else:
                break
        
        return min_len


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l,r = 0,len(arr) - 1
        while l < r and arr[l] <= arr[l + 1]:
            l += 1
        if l == len(arr) - 1:
            return 0
        
        while r >= 0 and arr[r] >= arr[r - 1]:
            r -= 1
            
        toRemove = min(len(arr) - l - 1,r)
        
        for iL in range(l + 1):
            if arr[iL] <= arr[r]:
                toRemove = min(toRemove,r - iL - 1)
                l += 1
            elif r < len(arr) - 1:
                r += 1
            else:
                break
           
        return toRemove

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        #https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/discuss/830480/C%2B%2B-O(N)-Sliding-window-Explanation-with-Illustrations
        #这道题是two pointer类型题目
        #大体的逻辑就是左边一个pointer，右边一个pointer
        left = 0
        right = len(arr) - 1
        
        #left向右走，如果left+1指向的数字大于等于left就一直走
        #如果left一路走到了end，那就说明原list就是sorted的，那就直接return
        while left + 1 <= len(arr) - 1 and arr[left] <= arr[left+1]:
            left += 1
        
        if left == right:
            return 0
        
        #right同理向左走，如果right-1小于等于right就继续走
        while right - 1 >= 0 and arr[right] >= arr[right - 1]:
            right -= 1
            
        #然后先处理两边 就是当0到right-1 或者 left+1到end 其中一个去掉，也就是去掉两边
        #在这种情况下 无论怎么移除中间的部分 都没有办法使两边组合起来成为递增
        #这种情况就像[6,7,8,9,10,3,5,20,4,1,2,3]
        #left指向10，right指向1 -- 因为只能移除一个subarry所以要从 6到20 和 3到3 中选一个
        
        
        #所以如果是这种case，那就先要计算两个边较小的那个
        #right就是0到right -1 index的长度
        #len(arr)- 1 - left 就是 end - left 也就是 left + 1到end index的长度  
        min_sublen = min(right, len(arr)- 1 - left)
        
        #然后就可以开始进行中间情况的运算
        #大概就是在这种情况下我们left和right要进行移动，然后找到最短的中间subarray，使得该array去掉后左右两边能成为递增array
        #大概的操作就是比较 两个指针lp和rp 从0到left 和 从right到end
       
        #如果lp小于rp了，那就说明去掉lp和rp中间范围就是递增，此时就可以计算下subarr长度，然后进行比较，留下最小的那个。然后lp向右移动一位再继续比较
        #知道lp到达了left，或者rp到达了end，就停止 返回最短的subarry长度
        lp = 0
        rp = right
        
        #如果lp大于rp，那就说明lp太大了，rp向右移动一位
        while lp <= left and rp <= len(arr) - 1:
            if arr[lp] > arr[rp]:
                rp += 1
            #如果lp小于rp了，那就说明去掉lp和rp中间范围就是递增，此时就可以计算下subarr长度，然后进行比较，留下最小的那个。然后lp向右移动一位再继续比较
            else:
                min_sublen = min(min_sublen, rp-lp-1)
                lp += 1
        
        return min_sublen

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l,r = 0, len(arr)-1
        while l < r and arr[l+1] >= arr[l]:
            l += 1
        if l == len(arr)-1:
            return 0
        while r > 0 and arr[r-1] <= arr[r]:
            r -= 1
            
        toRemove = min(len(arr)-1-l,r)
        
        for iL in range(l+1):
            if arr[iL] <= arr[r]:
                toRemove = min(toRemove, r-iL-1)
            elif r < len(arr)-1:
                r += 1
            else:
                break
        return toRemove


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        stack = [(len(arr)-1, arr[-1])]
        
        for i in range(len(arr)-2, -1, -1):
            if arr[i] <= arr[i+1]:
                stack.append([i, arr[i]])
            else:
                break
        
        min_len = len(arr)-len(stack)
        
        for i in range(len(arr)):
            if i == 0 or arr[i] >= arr[i-1]:
                while len(stack) > 0 and (stack[-1][1] < arr[i] or stack[-1][0] <= i):
                    stack.pop()

                if len(stack) > 0:
                    min_len = min(min_len, stack[-1][0]-i-1)
                else:
                    min_len = min(min_len, len(arr)-i-1)
            else:
                break
        
        return min_len


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        i = 1
        if len(arr) <= 1:
            return 0
        while i < n:
            if arr[i] < arr[i-1]:
                break
            i += 1
        max_len = i
        if max_len == n:
            return 0
        ini_ind = i - 1
        end_ind = 1
        while ini_ind >= 0:
            if arr[ini_ind] <= arr[-1]:
                break
            ini_ind -= 1
        max_len = max(max_len, ini_ind + end_ind + 1)
        while arr[-end_ind-1] <= arr[-end_ind]:
            while ini_ind >= 0:
                if arr[ini_ind] <= arr[-end_ind-1]:
                    break
                ini_ind -= 1
            end_ind += 1
            max_len = max(max_len, ini_ind + end_ind + 1)
        return n - max_len

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        start, end = 0, 0
        for i in range(1, len(arr)):
            if arr[i] < arr[i - 1] or (start and arr[i] < arr[start - 1]):
                if not start:
                    start = i
                end = i
        if start > 0:
            if arr[end] >= arr[start - 1]:
                end -= 1
            curr_opt = end - start + 1
        else:
            curr_opt = end - start
        for i in range(start):
            start -= 1
            while (end == len(arr) - 1 or arr[end] <= arr[end + 1]) and ((start and arr[end] >= arr[start - 1]) or not start):
                end -= 1
            curr_opt = min(curr_opt, end - start + 1)
        return curr_opt
            
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        l, r = 0, n-1
        while 0 < r and arr[r-1] <= arr[r]:
            r -= 1
        
        ret = r
        while l == 0 or l < n and arr[l-1] <= arr[l]:
            while r<=l or r < n and arr[r] < arr[l]:
                r += 1
            ret = min(ret, r - l - 1)
            l += 1
             
        return ret

from typing import *
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        i, j = 0, n - 1
        while i < n - 1 and arr[i] <= arr[i + 1]:
            i += 1
        if i == n - 1:
            return 0
        while j > i and arr[j - 1] <= arr[j]:
            j -= 1
        res = min(n - i - 1, j)
        oldi = i
        oldj = j
        i = 0
        while i <= oldi and j < n:
            if arr[i] <= arr[j]:
                res = min(res, j - i - 1)
                i += 1
            else:
                j += 1
        return res

print(Solution().findLengthOfShortestSubarray([1,3,2,4])) # 1
print(Solution().findLengthOfShortestSubarray([1,2,3,10,4,2,3,5])) # 3

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        
        desc_idx = []
        for idx in range(len(arr)):
            if idx > 0 and arr[idx] < arr[idx - 1]:
                desc_idx.append(idx-1)
        
        if len(desc_idx) == 0:
            return 0
        ans = len(arr)
        start, end = desc_idx[0], desc_idx[-1]
        shift_range = [0 , 1]
        for shift1 in shift_range:
            for shift2 in shift_range:
                left = arr[:start+shift1]
                right = arr[end+1+shift2:]
                left_extend = -1
                right_extend = -1


                if len(left) == 0:
                    right_extend = 0
                else:
                    for idx in range(len(right)):
                        if right[idx] >= left[-1]:
                            right_extend = idx
                            break
                    if right_extend == -1:
                        right_extend = len(right)

                if len(right) == 0:
                    left_extend = 0
                else:
                    for idx in range(len(left)):
                        if left[-(idx+1)] <= right[0]:
                            left_extend = idx
                            break
                    if left_extend == -1:
                        left_extend = len(left)
                
                ans = min(ans, min(left_extend, right_extend) +  (end+1+shift2) - (start + shift1))
                #extend.append(left_extend)
                #extend.append(right_extend)
        
        #print(extend, ans, desc_idx)
        #ans += min(extend)
        return ans
            
            


class Solution:

    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # [1,2,3,10,4,2,3,5]
        
        r = len(arr) - 1 
        while r >0 and arr[r] >= arr[r-1]:
            r -= 1
            
        ret = r # worst case, remove all left
        l = 0
        
        for l in range(len(arr)):
            if l>0 and arr[l] < arr[l-1]:
                break
            if l >= r:
                r += 1
            while r < len(arr) and arr[l] > arr[r] :
                r +=1
            

            ret = min(ret, r-l-1)
                
            
            
        return ret
            

        

        

        
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        for i in range(n):
            if i+1 >= n or arr[i] > arr[i+1]:
                l_end = i
                break
        for i in range(n-1,-1,-1):
            if i-1 < 0 or arr[i-1] > arr[i]:
                r_start = i
                break
        if r_start <= l_end: return 0
        i, j = 0, r_start
        res = min(n-(l_end+1),r_start)
        for i in range(l_end+1):
            while j < n and arr[i] > arr[j]:
                j += 1
            res = min(res, j-i-1)
        return res

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        
        '''
        [1,2,3,10,4,2,3,5]
        3
        
        '''
        def doesExist(arr, size, prefix, suffix):
            if size >= suffix or (len(arr) -1 - size) <= prefix:
                return True
            for i in range(len(arr) - size - 1):
                if prefix < i:
                    break
                else:
                    j = i + size + 1
                    if arr[i] <= arr[j] and j >= suffix:
                        return True
            return False
          
        prefix = 0
        suffix = len(arr) - 1
        for i in range(1, len(arr)):
            if arr[i-1] <= arr[i]:
                prefix = i
            else:
                break
        
        for i in range(len(arr) - 1, 0, -1):
            if arr[i-1] <= arr[i]:
                suffix = i - 1
            else:
                break
                
        l = 0
        r = len(arr) - 1
        optimal = r
        while l <= r:
            mid = (l + r) // 2
            if doesExist(arr, mid, prefix, suffix):
                optimal = mid
                r = mid - 1
            else:
                l = mid + 1
        return optimal
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        #sliding window
        #find the first element which is smaller than the previous one
        start_f = 0
        while start_f<len(arr)-1:
            if arr[start_f+1] >= arr[start_f]:
                start_f += 1
            else:
                break
        
        # if already sorted, end_f is the last element
        if start_f == len(arr)-1:
            return 0
        
        #find the end point that let end+1 element > start_f element
        end_f = len(arr)-1
        
        if arr[-1] < arr[start_f]:
            end_f = len(arr)
        else:
            while end_f-1 >= 0 and arr[end_f-1] >= arr[start_f]:
                if arr[end_f-1] <= arr[end_f]: # 逐渐在变小
                    end_f -= 1
                else: #not sorted， 前面一个数比较大了，那么在往前退，会导致第二部分不是sort的
                    break
                    
        #start,end 是需要remove的
        start, end = start_f+1, end_f-1
        
        ans = end-start+1
        
        #逐渐把start往前1，看能不能得到更小的值
        while start >= 0:
            start -= 1
            while start ==0 or arr[end] >= arr[start-1]: # start ==0的时候就没有第一部分了
                
                if end == len(arr)-1 or arr[end] <= arr[end+1]: # end最大时，就没有第二部分了
                    end -= 1
                    ans = min(ans, end-start+1)
                else:
                    break
        return ans
        
            
        


import bisect
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        start, end = 0, len(arr)-1
        while start < len(arr)-1:
            if arr[start] > arr[start+1]:
                break
            start += 1                
        if start == len(arr)-1:
            return 0 
        while end > 0:
            if arr[end] < arr[end-1]:
                break
            end -= 1                                
        best_dist = end
        for i in range(start, -1, -1):
            j = bisect.bisect_left(arr, arr[i], end, len(arr))
            dist = j - i - 1
            best_dist = min(best_dist, dist)
        return best_dist            



class Solution(object):
    def findLengthOfShortestSubarray(self, A):
        N = len(A)
        j = N - 1
        while j and A[j] >= A[j - 1]:
            j -= 1
        # A[j:] is monotone increasing
        
        ans = j
        for i in range(j):
            if i and A[i] < A[i-1]:
                break
            # A[..i] is monotone increasing
            while j < N and A[i] > A[j]:
                j += 1
            # j is the smallest such that A[i] <= A[j]
            # Remove A[i+1..j-1] which has length j - i - 1
            ans = min(ans, j - i - 1)
        
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # find the first inst in left side where arr[i] < arr[i-1]
        # next, find the first inst in right side where arr[j] < arr[j-1]
        # next, we start i from 0, j at j
        # we shrink window if arr[i] <= arr[j]
        # we expand window if arr[i] > arr[j]
        # we store the size of the window to ans
        n = len(arr)
        left = 0
        while (left + 1 < n and arr[left] <= arr[left + 1]):
            left += 1
        if left == n - 1: return 0
        
        right = n-1
        while (right > left and arr[right - 1] <= arr[right]):
            right -= 1;
        
        ans = min(n - left - 1, right)
        i, j = 0, right
        while i <= left and j < n:
            if arr[i] <= arr[j]:
                ans = min(ans, j - i - 1)
                i += 1
            else:
                j+=1
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        
        def lowerbound(left, right, target):
            while left < right:
                mid = left + (right - left) // 2
                
                if arr[mid] == target:
                    right = mid
                elif arr[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            
            return left
        
        N = len(arr)
        
        i = 0
        while i + 1 < N and arr[i] <= arr[i + 1]:
            i += 1
        
        if i == N - 1:
            return 0
        
        j = N - 1
        while j - 1 >= 0 and arr[j] >= arr[j - 1]:
            j -=1
            
        if j == 0:
            return N - 1
        
        result = min(N - (N-j), N - i - 1)
        
        for k in range(i + 1):
            l = lowerbound(j, len(arr), arr[k])
            result = min(result, l - (k + 1))
        
        return result

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l = 0
        longest_array = 0
        while l < len(arr)-1 and arr[l+1] >= arr[l]:
            l += 1
        longest_array = l+1

        r = len(arr)-1
        while r > 0 and arr[r] >= arr[r-1]:
            r -= 1
        longest_array = max(longest_array, len(arr)-r)
        #print(f'{l} {r}')

        p1 = 0
        p2 = r

        while p1 <= l and p2 < len(arr):
            if arr[p1] <= arr[p2]:
                longest_array = max(longest_array, p1 + len(arr)-p2+1)
                p1 += 1
            else:
                p2 += 1

        if len(arr)-longest_array < 0:
            return 0
    
        return len(arr) - longest_array

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        arr = [0] + arr + [float('inf')]
        left = 0
        right = len(arr) - 1
        
        while left != right:
            if arr[left + 1] < arr[left]:
                break
            left += 1
            
        while left != right:
            if arr[right - 1] > arr[right]:
                break
            right -= 1
            
        if right == left: return 0
        
        return search(left, right, arr)
        

def search(leftidx, rightidx, arr):
    if arr[rightidx] >= arr[leftidx]: return rightidx - leftidx - 1
    leftsearch = rightsearch = midsearch = len(arr)
    if leftidx > 0:
        leftsearch = search(leftidx - 1, rightidx, arr)
    if rightidx < len(arr) - 1:
        rightsearch = search(leftidx, rightidx + 1, arr)
    if leftidx > 0 and rightidx < len(arr) - 1:
        midsearch = search(leftidx - 1, rightidx + 1, arr)
    
    return min(leftsearch, rightsearch, midsearch)

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n=len(arr)
        left,right=-1,-1
        for i in range(n-1):
            if arr[i]>arr[i+1]:
                left=i+1
                break
        if left==-1:
            return 0
        for j in range(n-1, 0, -1):
            if arr[j]<arr[j-1]:
                right=j-1
                break
        if right==-1:
            return 0
        
        ans=min(right+1, n-left)
        i=0
        for j in range(right+1,n):
            while i<left and arr[i]<=arr[j]:
                i+=1
            ans=min(ans, j-i)
            if i==left:
                break
        return ans



class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n=len(arr)
        ndpreflen=1
        for i in range(1,n):
            if arr[i]<arr[i-1]: break
            ndpreflen+=1
        ndsufflen=1
        for i in range(1,n):
            if arr[n-1-i]>arr[n-i]: break
            ndsufflen+=1
        if ndpreflen+ndsufflen>n: return 0
        sufffirstkeep_idx=n-ndsufflen
        ans=min(n-ndpreflen,n-ndsufflen)
        for preflastkeep_idx in range(ndpreflen):
            while sufffirstkeep_idx<n and arr[sufffirstkeep_idx]<arr[preflastkeep_idx]:
                sufffirstkeep_idx+=1
            if sufffirstkeep_idx==n: break
            ans=min(ans,sufffirstkeep_idx-preflastkeep_idx-1)
        return ans

class Solution:
    '''
    https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/discuss/830480/C%2B%2B-O(N)-Sliding-window-Explanation-with-Illustrations
    1,2,3,10,4,2,3,5]
    1 2 2  3 3 4 5 10
    '''
    def findLengthOfShortestSubarray(self, A: List[int]) -> int:
        N = len(A)
        left, right = 0, N - 1
        while left + 1 < N and A[left] <= A[left + 1]:
            left += 1
        if left == N - 1: # not decreasing already 
            return 0
        
        while right > left and A[right - 1] <= A[right]:
            right -= 1
            
        ans = min(N - left - 1, right)
        i, j = 0, right
        while i <= left and j < N:
            if A[j] >= A[i]:
                # can remove
                ans = min(ans, j - i - 1)
                i += 1 # then shrink silde window
            else:
                # enlarge slide window
                j += 1
        return ans

from bisect import bisect_right

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        arr = [float('-inf')] + arr + [float('inf')]
        if arr == sorted(arr): return 0
        N = len(arr)
        negatives = [None, None]
        for i in range(1, N):
            diff = arr[i] - arr[i-1]
            if diff < 0:
                if negatives[0] is None:
                    negatives[0] = i
                negatives[1] = i
        ans = float('inf')
        for j in range(negatives[1], N):
            idx = bisect_right(arr, arr[j], hi=negatives[0])
            ans = min(ans, j - idx)
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        if n==0:
            return 0
        l, r = 0,n-1
        while l < n-1 and arr[l] <= arr[l+1]:
             l += 1
        while r > 0 and arr[r-1] <= arr[r]:
            r -= 1
        nums_to_rm = min(n - 1 - l, r)
        for c in range(l+1):
            if arr[c] <= arr[r]:
                nums_to_rm = min(nums_to_rm, max(0,r-c-1))
            else:
                if r < n-1:
                    r += 1
                else:
                    break
        
        return nums_to_rm


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if not arr:
            return 0
        a,temp= [],[]
        temp.append(arr[0])
        for i in range(1,len(arr)):
            if arr[i] - arr[i - 1] >= 0:
                temp.append(arr[i])
            else:
                a.append(temp)
                temp = []
                temp.append(arr[i])
        if temp:
            a.append(temp)
        if len(a)<=1:
            return 0
        else:
            deletelen=[]
            a0,a_1=a[0],a[-1]
            deletelen.append(len(arr)-len(a0))
            deletelen.append(len(arr)-len(a_1))
            if a0[-1]<=a_1[0]:
                deletelen.append(len(arr)-len(a0)-len(a_1))
            else:
                for i in range(len(a_1)):
                    for j in range(len(a0)-1,-1,-1):
                        if a_1[i]>=a0[j]:
                            deletelen.append(len(arr) - len(a0) - len(a_1)+i+(len(a0)-j-1))
                            break
            return min(deletelen)

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if arr == sorted(arr):
            return 0
        L = len(arr)
        
        left = [arr[0]]
        right = [arr[-1]]
        
        for i in range(1, L):
            if arr[i] >= left[-1]:
                left += [arr[i]]
            else:
                break
        
        for i in range(L-2, -1, -1):
            if arr[i] <= right[0]:
                right.insert(0, arr[i])
            else:
                break
        
        while len(left)-1 >= L-len(right) and left[-1] == right[0]:
            left.pop(-1)
        print((left, right, L))
                
        ret = 0
        arr_len = 0
        for i in range(len(left)):
            for j in range(len(right)):
                temp = 0
                if left[i] <= right[j]:
                    temp = i+1+len(right)-j
                    break
            # if left[i] in right:
            #     idx_right = right.index(left[i])
            #     temp = i+1+len(right)-idx_right
            # else:
            #     idx_right = len(right)-1
            #     temp = 0
            arr_len = max(arr_len, temp)
        
        return L-max(len(left), len(right), arr_len)


class Solution:
    # O(n)
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:

        # determine right sorted subarray
        r = len(arr) - 1 
        while r >0 and arr[r] >= arr[r-1]:
            r -= 1
        
        # r == 0 means array is sorted
        if r == 0:
            return 0
        
        # now determine left sorted subarray that can be merged with right
        ret = r # set ret to worst case, remove all left 
        l = 0
        for l in range(len(arr)):
            # if left subarry is not in order anymore, stop, can't do better
            if l>0 and arr[l] < arr[l-1]:
                break
            
            # if arr[l] is larger than the left edge of right sorted subarray, 
            # push the edge to the right
            # why this work? Is it OK to push to the right? We won't consider
            # arr[i+1] and arr[r].
            # It's OK! We don't have to consider arr[i+1] and arr[r].
            # if arr[i] is larger than the left edge, arr[next i] is larger too!
            # so it won't be the possible answer
            while r < len(arr) and arr[l] > arr[r] :
                r +=1

            ret = min(ret, r-l-1)

        return ret
            

        

        

        
        


from collections import deque
import bisect

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l, r = deque([]), deque([])
        for i, x in enumerate(arr):
            if len(l) == 0 or x >= l[-1]:
                l.append(x)
            else:
                break
        for i, x in enumerate(arr[::-1]):
            if len(r) == 0 or x <= r[0]:
                r.appendleft(x)
            else:
                break
        if len(l) == len(arr):
            return 0
        a, b = len(l), len(r)
        ans = b
        for i, x in enumerate(l):
            idx = bisect.bisect_left(r, x)
            ans = max(ans, i + 1 + b - idx)
        
        return len(arr) - ans


import bisect
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        start = None
        for i in range(0, len(arr)-1):
            if arr[i] > arr[i+1]:
                start = i
                break
                
        if start == None:
            return 0 
        
        for i in range(len(arr)-1, 0, -1):
            if arr[i] < arr[i-1]:
                end = i
                break

        best_dist = end
        for i in range(start, -1, -1):
            j = bisect.bisect_left(arr, arr[i], end, len(arr))
            dist = j - i - 1
            best_dist = min(best_dist, dist)
            
        return best_dist            




class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # Find the longest monotonically non-decreasing prefix array in [0, i]
        n = len(arr)
        l = 1
        while l < n and arr[l-1] <= arr[l]:
            l += 1
        l -= 1  
        if l >= n - 2:
            return n - 1 - l
                
        # Find the longest monotonically non-decreasing suffix array in [j, n - 1]
        r = n - 2
        while r >= 0 and arr[r] <= arr[r+1]:
            r -= 1
        r += 1
        if r <= 1:
            return r
    
        # Start off with min of either left or right side removed as the min_to_move
        min_to_remove = min(n - 1, n - 1 - (l + 1) + 1, r)
        # Try to merge [0..i] from the left into [r..n-1]. If it doesn't work, 
        # push r forward and try again, until we run out of either room for i to expand
        # toward the right or for r to push forward to the right.
        i = 0
        while i < l + 1:
            if arr[i] <= arr[r]:
                min_to_remove = min(min_to_remove, r - i - 1)
                i += 1
            elif r < n - 1:
                r += 1
                # i += 1 # More intuitive and less subtle to NOT increment i

                # Why? Because if after i gets incremented a few times to
                # i' such that arr[i'] <= arr[r], then arr[r] must be >=
                # all elements in [i..i'-1] because elements in [0..l] are
                # non-decreasing. In other words as soon we hit line 
                # `if arr[i] <= arr[r]:` (after incrementing i a few times
                # without successfully finding some arr[r], arr[i] <= arr[r]),
                # all those values behind arr[i] can now be included in the merged
                # result.
            else:
                break
        
        return min_to_remove

        
    def findLengthOfShortestSubarray_bruteforce_bsearch(self, arr: List[int]) -> int:
        # Returns the smallest index `idx` such that arr[idx] >= val
        def bsearch(val, low, high):
            while low < high:
                mid = (low + high) // 2
                if arr[mid] >= val:
                    high = mid
                else:
                    low = mid + 1
            if val > arr[high]:
                return high + 1
            return high
        
        # Find the longest monotonically non-decreasing prefix array in [0, i]
        n = len(arr)
        curr_max = float('-inf')
        i = 0
        while i < n:
            if arr[i] < curr_max:
                break
            curr_max = arr[i]
            i += 1
        i -= 1  
        if i >= n - 2:
            return n - 1 - i
                
        # Find the longest monotonically non-decreasing suffix array in [j, n - 1]
        curr_min = float('inf')
        j = n - 1
        while j >= 0:
            if arr[j] > curr_min:
                break
            curr_min = arr[j]
            j -= 1
        j += 1
        if j <= 1:
            return j
        
        # For each value arr[k], in [0, i], find the `right_idx` into the suffix array in [j, n - 1]
        # such that arr[k] >= arr[right_idx]. We want to find the one that results in the longest
        # sequence [0..k] + [right_idx..n-1]
        min_to_remove = float('inf')
        for k in range(i, -1, -1):
            right_idx = bsearch(arr[k], j, n - 1)
            l = k + 1 + n - right_idx
            to_remove = n - l
            min_to_remove = min(min_to_remove, to_remove)
            
        # For each value arr[k], in [j, n-1], find the `left_idx` into the prefix array in [0, i]
        # such that arr[k] >= arr[left_idx - 1]. We want to find the one that results in the longest
        # sequence [0..left_idx-1] + [k..n-1]
        for k in range(j, n):
            left_idx = bsearch(arr[k], 0, i)
            l = left_idx + n - k
            to_remove = n - l
            min_to_remove = min(min_to_remove, to_remove)
        
        return min_to_remove
        
        

        
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        arr = [-float('inf')] + arr + [float('inf')]
        sorted_to = [False for _ in range(len(arr))]
        sorted_from = [False for _ in range(len(arr))]
        rev_arr = arr[::-1]
        last_sorted_to = -1
        first_sorted_from = -1
        shortest = float('inf')
        for idx, val in enumerate(arr):
            if idx == 0 or val >= arr[idx - 1]:
                sorted_to[idx] = True
                last_sorted_to = idx
            else:
                break
        for idx, val in enumerate(rev_arr):
            if idx == 0 or val <= rev_arr[idx - 1]:
                sorted_from[len(arr) - 1 - idx] = True
                first_sorted_from = len(arr) - 1 - idx
            else:
                break
        if arr == sorted(arr):
            return 0
        for i in range(last_sorted_to + 1):
            for j in range(first_sorted_from, len(arr)):
                if arr[j] >= arr[i]:
                    shortest = min(shortest, j - i - 1)
                    break
            shortest = min(shortest, len(arr) - i - 1)

        return shortest

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if arr == sorted(arr):
            return 0
        l = [arr[0]]
        r = [arr[-1]]
        for i in range(len(arr)):
            if arr[i + 1] >= arr[i]:
                l.append(arr[i + 1])
            else:
                break
        for i in range(len(arr) - 1, -1, -1):
            if arr[i] >= arr[i - 1]:
                r.insert(0, arr[i - 1])
            else:
                break
        res1 = len(arr) - len(r)
        res2 = len(arr) - len(l)
        j = 0
        for i in range(len(l)):
            while j < len(r) and l[i] > r[j]:
                j += 1
            if j == len(r):
                j -= 1
            p = i
            while p < len(l) and l[p] <= r[j]:
                p += 1
            p -= 1            
            return min(res1, res2, len(arr) - (p + 1 + len(r) - j))

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l,r = 0,len(arr) - 1
        while l < r and arr[l] <= arr[l + 1]:
            l += 1
            
        if l == len(arr) - 1:
            return 0
        while r >= 0 and arr[r] >= arr[r - 1]:
            r -= 1
            
        toRemove = min(len(arr) - l - 1,r)
        
        for iL in range(l + 1):
            if arr[iL] <= arr[r]:
                toRemove = min(toRemove,r - iL - 1)
            elif r < len(arr) - 1:
                r += 1
        return toRemove

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        
        def lowerbound(left, right, target):
            while left < right:
                mid = left + (right - left) // 2
                
                if arr[mid] == target:
                    right = mid
                elif arr[mid] < target:
                    left = mid + 1
                else:
                    right = mid
                
            return left
        
        
        N = len(arr)
        
        # find the longest ascending array on the left side
        i = 0
        while i + 1 < N and arr[i] <= arr[i+1]:
            i += 1
        
        if i == N - 1:
            # it is already in ascending order
            return 0
        
        # find the longest ascending array on the right side
        j = N - 1
        while j - 1 >= 0 and arr[j] >= arr[j-1]:
            j -= 1
        
        if j == 0:
            # the entire array is in decending order
            return N - 1
        
        # keep ascending array on right side or left side
        result = min(N - (N - j), N - i -1)
        
        
        # find the shortest unordered subarray in the middle 
        for k in range(i+1):
            l = lowerbound(j, len(arr), arr[k])
            result = min(result, l - (k + 1))
        
        
        return result

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        if arr == sorted(arr):
            return 0
        l = [arr[0]]
        r = [arr[-1]]
        for i in range(len(arr)):
            if arr[i + 1] >= arr[i]:
                l.append(arr[i + 1])
            else:
                break
        for i in range(len(arr) - 1, -1, -1):
            if arr[i] >= arr[i - 1]:
                r.insert(0, arr[i - 1])
            else:
                break
        res1 = len(arr) - len(r)
        res2 = len(arr) - len(l)
        res3 = len(arr)
        if l[-1] <= r[0]:
            res3 = len(arr) - len(l) - len(r)
        res = min(res1, res2, res3)
        j = 0
        for i in range(len(l)):
            while j < len(r) and l[i] > r[j]:
                j += 1
            if j == len(r):
                j -= 1
            p = i
            while p < len(l) and l[p] <= r[j]:
                p += 1
            p -= 1            
            return min(res, len(arr) - (p + 1 + len(r) - j))

class Solution:
    def findLengthOfShortestSubarray(self, A):
        # For each i, let's look at the best answer A[..i] + A[j..]
        # This requires:
        #   A[..i] monotone increasing;  (1)
        #   A[j..] monotone increasing;  (2)
        #   A[i] <= A[j]                 (3)
        
        # For each i, lets say the lowest (ie. best) such j = opt(i).
        # It turns out that opt(i) is monotone increasing, so we can use
        # two pointers.
        
        N = len(A)
        j = N - 1
        while j and A[j - 1] <= A[j]:
            j -= 1
        
        ans = j
        # j is lowest such that A[j..] is monotone increasing
        for i in range(j):
            if i and A[i-1] > A[i]:
                break
            while j < N and A[i] > A[j]:
                j += 1
            # Now, j = opt(i): ie., the lowest j such that
            # all 3 conditions (1), (2), (3) above are satisified.
            ans = min(ans, j - i - 1)
        
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        answer = n
        curr = arr[0]
        start = 1
        while start < n:
            if arr[start] >= curr:
                curr = arr[start]
                start += 1
            else: break
        start -= 1
        if start == n-1:
            return 0
        curr = arr[n-1]
        end = n-2
        while end >= 0:
            if arr[end] <= curr:
                curr = arr[end]
                end -= 1
            else: break
        end += 1
        answer = min(answer, n-start-1, end)
        l, r = 0, end
        while r < n and l <= start:
            if arr[l] <= arr[r]:
                answer = min(answer, r-l-1)
                l += 1
            else:
                r += 1
        return answer 


class Solution:
    def findLengthOfShortestSubarray(self, arr):
        n = len(arr)
        left, right = 0, n - 1
        while left < n - 1 and arr[left] <= arr[left + 1]:
            left += 1
        if left == n - 1:
            return 0
        while right > 0 and arr[right - 1] <= arr[right]:
            right -= 1
        res = min(n - left - 1, right)
        j = right
        for i in range(left + 1):
            while j <= n - 1 and arr[i] > arr[j]:
                j += 1
            if j <= n - 1:
                res = min(res, j - i - 1)
        return res
                

            


                
                
            


class Solution:
    def findLengthOfShortestSubarray(self, a: List[int]) -> int:
        n = len(a)
        if all(a[i] >= a[i - 1] for i in range(1, n)):
            return 0
        d = {x: i + 1 for i, x in enumerate(sorted(set(a)))}
        a = [d[x] for x in a]
        last = [0] * (len(d) + 1)
        prev = -1
        for i, x in enumerate(a):
            if x < prev: break
            last[x] = i + 1
            prev = x

        for i in range(1, len(d) + 1):
            if last[i] == 0:
                last[i] = last[i - 1]

        ans = last[-1]
        prev = 1e100
        for i, x in enumerate(a[::-1]):
            if prev < x: break
            ans = max(ans, i + 1 + last[x])
            prev = x
        return n - ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        N = len(arr)

        left_idx = 0
        while left_idx < N - 1 and arr[left_idx] <= arr[left_idx+1]:
            left_idx += 1

        if left_idx == N - 1:
            return 0

        right_idx = N - 1
        while right_idx > 1 and arr[right_idx] >= arr[right_idx - 1]:
            right_idx -= 1

        r = min(N - 1 - left_idx, right_idx)

        i = 0
        j = right_idx 
        while i <= left_idx and j <= N - 1:
            if arr[j] >= arr[i]:
                r = min(r, j - i - 1)
                i += 1
            else:
                j += 1
        return r

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        inc_idx = 0
        for i in range(1, len(arr)):
            if arr[i] >= arr[i-1]:
                inc_idx += 1
            else:
                break
    
        if inc_idx == len(arr) - 1:
            return 0
        
        dec_idx = len(arr) - 1
        for i in range(len(arr) - 2, -1, -1):
            if arr[i] <= arr[i+1]:
                dec_idx -= 1
            else:
                break
        
        l = self.helper(arr[:inc_idx+1], arr[dec_idx:])
        return len(arr) - l
        
        
    def helper(self, arr1: List[int], arr2: List[int]):
        print((arr1, arr2))
        i, j = 0, 0
        l = 0
        while i < len(arr1) and j < len(arr2):
            while j < len(arr2) and arr1[i] > arr2[j]:
                j += 1
            if j == len(arr2):
                break
            
            l = max(l, i + 1 + len(arr2) - j)
            i += 1

        return max(len(arr1), len(arr2), l)
        


# 1040

class Solution:
  def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
    n = len(arr)
    left_good = [True,]
    right_good = [True,]
    for i in range(1, n):
      if arr[i] >= arr[i-1]:
        left_good.append(True)
      else:
        break
        
    left_good.extend([False] * (n - len(left_good)))

    for i in range(n-2, -1, -1):
      if arr[i] <= arr[i+1]:
        right_good.append(True)
      else:
        break
        
    right_good.extend([False] * (n - len(right_good)))
    right_good.reverse()
    
    high = n
    low = 0
    
    def enough(sz):
      if sz == n:
        return True
      if sz == 0:
        return left_good[n-1]
      for begin in range(n):
        end = begin + sz - 1
        if end >= n:
          return False
        a = begin - 1
        b = end + 1
        if (a < 0 or left_good[a]) and (b == n or right_good[b]) and ((not 0 <= a < b < n) or (arr[a] <= arr[b])):
          #print('found ', begin, sz)
          return True
        
      return False
    
    #print(left_good, right_good)
    
    while low <= high:
      cur = int((low + high) / 2) # low + (high - low) / 2
      #print('trying', cur, enough(cur), low, high)
      if enough(cur):
        high = cur - 1
      else:
        low = cur + 1
    
    return low

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l = 0
        r = len(arr)-1
        while l < len(arr)-1 and arr[l+1] >= arr[l]:
            l +=1
        if l == len(arr)-1:
            return 0
        while r > 0 and arr[r-1] <= arr[r]:
            r -=1
        
        res = min(len(arr)-l-1, r)
        
        i, j = 0, r
        while i <= l and j < len(arr):
            if arr[i] <= arr[j]:
                res = min(res, j - i - 1)
                i +=1
            else:
                j +=1
                
        return res


class Solution:

    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # [1,2,3,10,4,2,3,5]
        
        r = len(arr) - 1 
        while r >0 and arr[r] >= arr[r-1]:
            r -= 1
            
        ret = r # worst case, remove all left
        l = 0
        
        for l in range(len(arr)):
            if l>0 and arr[l] < arr[l-1]:
                break
            if l == r:
                r += 1
            while r < len(arr) and arr[l] > arr[r] :
                r +=1
            

            ret = min(ret, r-l-1)
                
            
            
        return ret
            

        

        

        
        


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        l = 0
        r = len(arr) - 1
        while l < r and arr[l] <= arr[l + 1]:
            l += 1
        if l == r:
            return 0
        
        while r > 0 and arr[r] >= arr[r - 1]:
            r -= 1
            
        min_remove = min(len(arr) - l - 1, r)
        
        for i in range(l + 1):
            if arr[i] <= arr[r]:
                min_remove = min(min_remove, r - i - 1)
            elif r < len(arr) - 1:
                r += 1
            else:
                break
                
        return min_remove

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        inc_idx = 0
        for i in range(1, len(arr)):
            if arr[i] >= arr[i-1]:
                inc_idx += 1
            else:
                break
    
        if inc_idx == len(arr) - 1:
            return 0
        
        dec_idx = len(arr) - 1
        for i in range(len(arr) - 2, -1, -1):
            if arr[i] <= arr[i+1]:
                dec_idx -= 1
            else:
                break
        
        l = self.helper(arr[:inc_idx+1], arr[dec_idx:])
        return len(arr) - l
        
        
    def helper(self, arr1: List[int], arr2: List[int]):
        print((arr1, arr2))
        i, j = 0, 0
        l = 0
        while i < len(arr1) and j < len(arr2):
            while j < len(arr2) and arr1[i] > arr2[j]:
                j += 1
            if j == len(arr2):
                break
            
            l = max(l, i + 1 + len(arr2) - j)
            print((i, j, l))
            i += 1

        return max(len(arr1), len(arr2), l)
        


class Solution:
    def findLengthOfShortestSubarray(self, a: List[int]) -> int:
        n = len(a)
        if all(a[i] >= a[i - 1] for i in range(1, n)):
            return 0
        d = {x: i + 1 for i, x in enumerate(sorted(set(a)))}
        a = [d[x] for x in a]
        last = [0] * (len(d) + 1)
        prev = -1
        for i, x in enumerate(a):
            if x < prev: break
            last[x] = i + 1
            prev = x
        # print(last)

        for i in range(1, len(d) + 1):
            if last[i] == 0:
                last[i] = last[i - 1]

        # print(a)
        # print(last)
        ans = last[-1]
        prev = 1e100
        for i, x in enumerate(a[::-1]):
            if prev < x: break
            print(prev, x, last[x], i)
            ans = max(ans, i + 1 + last[x])
            prev = x
        return n - ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        
        n = len(arr)
        
        p1 = p2 = -1
            
        for i in range(1, n):
            if arr[i] < arr[i - 1]:
                
                p2 = i
                
                if p1 == -1:
                    p1 = i
                    
        if p1 == -1:
            return 0
        
        
        def chk(l):
            
            nonlocal p1
            nonlocal p2
            
            # print (p1, p2)
            
            if l >= p2:
                return True
                                    
            n = len(arr)
            
            for i in range(n):
                                
                if i > p1:
                    return False
                
                if i + l >= n:
                    return True
                                
                if i + l < p2:
                    continue
                
                if arr[i - 1] <= arr[i + l]:
                    return True
                    
            return False
        
        # print (chk(8))
        
        # return 0

        l = 0
        r = n
        
        while l < r:
            
            mid = (l + r) // 2
            
            if chk(mid):
                r = mid
            else:
                l = mid + 1
                
        return l


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        
        l = 0
        r = n-1
        ans = 0
        
        while l < n-1 and arr[l] <= arr[l+1]:
            l+=1
        if l == n-1:
            return 0
        
        ans = n - l - 1
        
        while r >= l and arr[r] >= arr[r-1]:
            r-=1
              
        if r == 0:
            return n-1
        ans = min(ans,r)
        i = 0
        j = r
        
        while i <= l and j < n:
            if arr[i] <= arr[j]:
                ans = min(ans, j-i-1)
                i+=1
            else:
                j+=1
                
        return ans

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        i, j = 0, n - 1
        while i < n - 1 and arr[i] <= arr[i + 1]:
            i += 1
        if i == n - 1: return 0 # sorted
        while j > 0 and arr[j] >= arr[j - 1]:
            j -= 1
        if j == 0: return n - 1 # reversely sorted
        
        res = min(n - 1 - i, j) # leaving prefix, or suffix after removing
        
        # to merge prefix and suffix
        # binary search also works here but worse time complexity:
        # need to search each of prefix in suffix (or the other way)
        # checking only end of prefix and head of suffix is not enough
        for k in range(i + 1):
            if arr[k] <= arr[j]:
                res = min(res, j - k - 1)
            elif j < n - 1:
                j += 1
            else:
                break
        return res

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        first, last = -1, -1
        length = len(arr)
        prev = float('-inf')
        for i in range(length):
            if arr[i] < prev:
                first = i
                break
            prev = arr[i]
        if first == -1:
            return 0
        after = float('inf')
        for i in range(length - 1, -1, -1):
            if arr[i] > after:
                last = i
                break
            after = arr[i]
            
        def helper(size):
            for i in range(length - size + 1):
                if i <= first and i + size > last:
                    if i + size == length or i == 0:
                        return True
                    if arr[i + size] >= arr[i - 1]:
                        return True
            return False
            
        low, high = 1, length - 1
        res = float('inf')
        while low <= high:
            mid = low + (high - low) // 2
            if helper(mid):
                res = min(res, mid)
                high = mid - 1
            else:
                low = mid + 1
        return res

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        i = 0
        pref = 1
        while i<len(arr)-1:
            if arr[i]<=arr[i+1]:
                pref+=1
            else:
                break
            i+=1
        
        j = len(arr)-1
        suff = 1
        while j>0:
            if arr[j]>=arr[j-1]:
                suff+=1
            else:
                break
            j-=1
        
        ans = min(len(arr)-pref,len(arr)-suff)
        pref = i
        suff = j
        i = 0
        j = suff
        while i<=pref and j<len(arr):
            if arr[i]<=arr[j]:
                ans = min(ans,j-i-1)
                i+=1
            elif arr[j]<arr[i]:
                j+=1
        # ans = min(ans,j-i-1)
        return  max(0,ans)


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        
        # 1 4 5 2 3 2 1 5 6 7
        # can be removed only in 3 types 
        # last, middle, front
        
        #front - what is the longest sorted array in the suffix
        #last - what is the longest sorted array in the prefix
        #middle - find the prefix and sufix sorting then see if then can be merged else 0
        
        n = len(arr)
        if n==1 or n==0:
            return 0
        front = 0
        a = -1
        b = -1
        last = 0
        middle = 0
        c = 1
        for i in range(1, n):
            if arr[i]>=arr[i-1]:
                c += 1
            else :
                a = i-1
                front = c
                break
        if c == n:
            a = n-1
            front = c
        c = 1
        for i in range(n-1,1,-1):
            if arr[i-1]<=arr[i]:
                c += 1
            else :
                last = c
                b = i
                break
        
        if c == n:
            b = 0
            last = c
        print((front, a, last, b))
        if b !=-1 and a!= -1 :
            for i in range(b,n):
                if arr[a] <= arr[i]:
                    middle = max(middle, front+(n-i))
                print((1,a,i))
            for i in range(0,a+1):
                if arr[i] <= arr[b]:
                    middle = max(middle, last+i+1)
                    print((2,i, b))
                    
                    
        return n-max(last,max(front,middle))


from typing import List


class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # 1. formulate two non-decreasing arr
        pre_len = 1
        while pre_len < len(arr):
            if arr[pre_len] < arr[pre_len - 1]:
                break
            pre_len += 1
        arr_a = arr[:pre_len]
        if len(arr_a) == len(arr):
            return 0

        arr_b = [arr[-1]]
        for j in range(len(arr) - 2, -1, -1):
            if arr[j] <= arr[j + 1]:
                arr_b.insert(0, arr[j])
            else:
                break
        # print(arr_a, arr_b)

        # 2. Loop through arr_a to find the ans
        ans = len(arr) - 1
        for i in range(len(arr_a)):
            j = self.binary_search(arr_b, arr_a[i])
            cut_length = len(arr) - (i + 1) - (len(arr_b) - j)
            ans = min(ans, cut_length)
        ans = min(ans, len(arr) - len(arr_a))
        ans = min(ans, len(arr) - len(arr_b))
        return ans

    # need to return the index i such that arr[i] >= num
    def binary_search(self, arr, num):
        low = 0
        high = len(arr) - 1
        ans = len(arr)
        while low <= high:
            mid = (low + high) // 2
            if arr[mid] >= num:
                ans = min(ans, mid)
                high = mid - 1
            else:
                low = mid + 1
        return ans


# leetcode submit region end(Prohibit modification and deletion)

def __starting_point():
    solution = Solution()
    assert (solution.findLengthOfShortestSubarray([1, 2, 3, 10, 4, 2, 3, 5]) == 3)
    assert (solution.findLengthOfShortestSubarray([5, 4, 3, 2, 1]) == 4)
    assert (solution.findLengthOfShortestSubarray([1, 2, 3]) == 0)
    assert (solution.findLengthOfShortestSubarray([13, 0, 14, 7, 18, 18, 18, 16, 8, 15, 20]) == 8)
    assert (solution.findLengthOfShortestSubarray([16, 10, 0, 3, 22, 1, 14, 7, 1, 12, 15]) == 8)

__starting_point()

class Solution:

    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        A=arr
        N = len(A)
        j = N-1
        while j >= 1 and A[j-1] <= A[j]:
            j -= 1
        res = j
        for i in range(N):
            if i >= j or (i > 0 and A[i] < A[i-1]): 
                break
            while j < N and A[i] > A[j]:    
                j += 1
            res = min(res, j-i-1)
        return res


        


class Solution:

    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # [1,2,3,10,4,2,3,5]
        
        r = len(arr) - 1 
        while r >0 and arr[r] >= arr[r-1]:
            r -= 1
            
        ret = r # worst case, remove all left
        l = 0
        
        for l in range(len(arr)):
            if l>0 and arr[l] < arr[l-1]:
                break
            if l >= r:
                break
            while r < len(arr) and arr[l] > arr[r] :
                r +=1
            print((l,r))

            ret = min(ret, r-l-1)
                
            
            
        return ret
            

        

        

        
        


from sortedcontainers import SortedList

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        last = -float('inf')
        
        sl = SortedList()
        
        for i, n in enumerate(arr):
            if n < last: break
            
            sl.add(n)
            
            last = n
                    
        ans = len(arr) - len(sl)
        last = float('inf')
        
        for i in range(len(arr)-1, 0, -1):
            if arr[i] > last: break
            
            last = arr[i]
            
            sl_idx = sl.bisect_right(arr[i])
                                    
            ans = min(ans, i - sl_idx)
        
        return max(0, ans)

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        left_idx, right_idx = 0, n - 1
        # edge case
        # left side
        while left_idx < n - 1 and arr[left_idx] <= arr[left_idx + 1]:
            left_idx += 1    
        # right side 
        while right_idx > 0 and arr[right_idx - 1] <= arr[right_idx]:
            right_idx -= 1
        nums_to_rm = min(n - left_idx - 1, right_idx)
        
        # print(nums_to_rm)
        
        # general case 
        for curr_idx in range(left_idx + 1):
            if arr[curr_idx] <= arr[right_idx]: 
                nums_to_rm = min(nums_to_rm, max(0, right_idx - curr_idx - 1))
                # print(nums_to_rm)
            else:
                # arr[curr_idx] > arr[right_idx]
                if right_idx < n - 1:
                    right_idx += 1
                else:
                    break
        # [1,2,3,10,4,2,3,5]
        # [5,4,3,2,1]
        # [1]
        return nums_to_rm

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
      
      pre = [True]
      pst = [True]
      for i in range(1, len(arr)):
        if pre[-1] and arr[i]>=arr[i-1]:
          pre.append(True)
        else: pre.append(False)
        
        if pst[-1] and arr[len(arr)-i-1]<=arr[len(arr)-i]:
          pst.append(True)
        else: pst.append(False)
      
      
      pst = pst[::-1]
      # print (pre)
      # print (pst)
      
      def isPoss(slen):
        for i in range(len(arr)-slen+1):
          j = i+slen
          
          if not i:
            if pst[j]: return True
          elif j>len(arr)-1:
            if pre[i-1]: return True
          else:
            if pre[i-1] and pst[j] and arr[i-1]<=arr[j]:
              return True
          
        return False
            
      # print (isPoss(1))
      l, r = 0, len(arr)
      res = r
      while l<=r:
        m = l + (r-l)//2
        if isPoss(m):
          res = min(m, res)
          r = m - 1
        else:
          l = m + 1
      return res

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # [start_f, end_f] is the first sorting part
        start_f, end_f = 0, 0
        while end_f+1 < len(arr):
            if arr[end_f+1] >= arr[end_f]:
                end_f += 1
            else:
                break
        # the entire array is sorted
        if end_f == len(arr)-1:
            return 0
        start_b, end_b = len(arr)-1, len(arr)-1
        # the last part is smaller than first part
        if arr[-1] < arr[end_f]:
            start_b = len(arr)
        else:
            while start_b-1 >= 0 and arr[start_b-1] >= arr[end_f]:
                if arr[start_b-1] <= arr[start_b]:
                    start_b -= 1
                else:
                    break
        print((start_f, end_f, start_b, end_b))
        start, end = end_f+1, start_b-1
        ans = end-start+1
        while start >= 0:
            start -= 1
            while start == 0 or arr[end] >= arr[start-1]:
                if end == len(arr)-1 or arr[end] <= arr[end+1]:
                    end -= 1
                    ans = min(ans, end-start+1)
                else:
                    break
        return ans