'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List
# 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

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        l, r = 0, n - 1
        # l < n-1: leaving at least one val for next pointer
        # find the rightmost l denoting the end of increasing subarray
        while l < n - 1 and arr[l] <= arr[l+1]:
            l += 1
        
        if l == n - 1: # increasing all the way
            return 0
        # shrinking right pointer, find leftmost pointer for r
        while r > l and arr[r-1] <= arr[r]:
            r -= 1
        # get rid of either left or right part
        res = min(n - l - 1, r) 
        # dealing with the middle ones
        i, j = 0, r
        while i <= l and j < n:
            if arr[i] <= arr[j]:
                res = min(res, j - i - 1)
                i += 1
            else:
                j += 1
        return res