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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Sorting

Amortized analysis

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
		if l == n:
			return 0
		for j in range(n - 2, -1, -1):
			if arr[j] > arr[j + 1]:
				r = j
				break
		ans = min(r + 1, n - l)
		i = 0
		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)

		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
		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
		print(i1, i2)
		remove = i2 - 1 - (i1 + 1) + 1
		ans = min(remove + i1 + 1, remove + len(arr) - i2)
		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 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:
		l = 0
		n = len(arr)
		while l < n - 1 and arr[l] <= arr[l + 1]:
			l += 1
		if l == n - 1:
			return 0
		r = len(arr) - 1
		while r > 0 and arr[r] >= arr[r - 1]:
			r -= 1
		left = n - (l + 1)
		right = 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:
		(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)
		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
		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
		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
		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:
		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
		r = n - 2
		while r >= 0 and arr[r] <= arr[r + 1]:
			r -= 1
		r += 1
		if r <= 1:
			return r
		min_to_remove = min(n - 1, n - 1 - (l + 1) + 1, r)
		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
			else:
				break
		return min_to_remove

	def findLengthOfShortestSubarray_bruteforce_bsearch(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:
		n = len(arr)
		(left, right) = (0, n - 1)
		while left < n - 1 and arr[left] <= arr[left + 1]:
			left += 1
		while right > 0 and arr[right] >= arr[right - 1]:
			right -= 1
		num_to_remove = min(n - left - 1, right)
		for curr in range(left + 1):
			if arr[curr] <= arr[right]:
				num_to_remove = min(num_to_remove, max(0, right - curr - 1))
			elif right < n - 1:
				right += 1
			else:
				break
		return num_to_remove


class Solution:

	def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
		r = len(arr) - 1
		while r > 0 and arr[r] >= arr[r - 1]:
			r -= 1
		ret = r
		l = 0
		for l in range(len(arr)):
			if l > 0 and arr[l] < arr[l - 1]:
				break
			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)
		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
			sol = max(sol, i + len(r) - j)
		return len(arr) - sol


class Solution:

	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 = [-1e+99] + arr + [1e+99]
		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


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
		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]
		while l < r:
			mid = (l + r) // 2
			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
				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)
		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:
		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
		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
		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:
		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:
		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:
			return True
		if i + j + k < n:
			return False
		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:
		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)
		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
		right = [False] * n
		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, nums: List[int]) -> int:
		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:

	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
		(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
		print((left_end, right_start))
		if left_end > right_start:
			return 0
		ret = min(N - left_end - 1, right_start)
		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
		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
				MIN = min(MIN, margin + a + b)
			else:
				i -= 1
				if j != LENGTH2:
					j += 1
		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
				MIN = min(MIN, margin + a + b)
			else:
				j += 1
				if i != 0:
					i -= 1
		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):
			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 = mid - 1
				else:
					lo = mid + 1
			lo = min(lo, n - 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)
		for i in range(1, n):
			if arr[i] >= arr[i - 1]:
				l += 1
			else:
				break
		for i in reversed(list(range(1, n))):
			if arr[i] >= arr[i - 1]:
				r -= 1
			else:
				break
		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)
		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):
				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])
					elif 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
		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)
		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 = 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)
			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


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:
		left = 0
		right = len(arr) - 1
		while left + 1 <= len(arr) - 1 and arr[left] <= arr[left + 1]:
			left += 1
		if left == right:
			return 0
		while right - 1 >= 0 and arr[right] >= arr[right - 1]:
			right -= 1
		min_sublen = min(right, len(arr) - 1 - left)
		lp = 0
		rp = right
		while lp <= left and rp <= len(arr) - 1:
			if arr[lp] > arr[rp]:
				rp += 1
			else:
				min_sublen = min(min_sublen, rp - lp - 1)
				lp += 1
		return min_sublen


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]))
print(Solution().findLengthOfShortestSubarray([1, 2, 3, 10, 4, 2, 3, 5]))


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))
		return ans


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:

		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:
		start_f = 0
		while start_f < len(arr) - 1:
			if arr[start_f + 1] >= arr[start_f]:
				start_f += 1
			else:
				break
		if start_f == len(arr) - 1:
			return 0
		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:
					break
		(start, end) = (start_f + 1, end_f - 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


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
		ans = j
		for i in range(j):
			if i and A[i] < A[i - 1]:
				break
			while j < N and A[i] > A[j]:
				j += 1
			ans = min(ans, j - i - 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)
		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)
		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


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))
			elif 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
			arr_len = max(arr_len, temp)
		return L - max(len(left), len(right), arr_len)


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


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:
		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 = 1e+100
		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)


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]):
					return True
			return False
		while low <= high:
			cur = int((low + high) / 2)
			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:
		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
			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
		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)
		(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 > 0 and arr[j] >= arr[j - 1]:
			j -= 1
		if j == 0:
			return n - 1
		res = min(n - 1 - i, j)
		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
		return max(0, ans)


class Solution:

	def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
		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:
		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
		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

	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

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:
		n = len(arr)
		(left_idx, right_idx) = (0, n - 1)
		while left_idx < n - 1 and arr[left_idx] <= arr[left_idx + 1]:
			left_idx += 1
		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)
		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))
			elif right_idx < n - 1:
				right_idx += 1
			else:
				break
		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]

		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
				elif pre[i - 1] and pst[j] and (arr[i - 1] <= arr[j]):
					return True
			return False
		(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