题解 | #合唱队#

import bisect



def inc_max(l):
    #初始化dp
    dp = [1]*len(l)
    #用于存放比较元素，将l中第一个元素放入
    arr = [l[0]]
    #从第二个开始遍历l中元素
    for i in range(1,len(l)):
        #如果l的元素比arr中末尾的元素要大，那么可以直接添加到序列后面，同时dp[i]的数量+1
        if l[i] > arr[-1]:
            arr.append(l[i])
            #arr的长度就是最小递增子序列的长度
            dp[i] = len(arr)
        else:
            # 实际:arr是一个顺序数组，下标越小，越靠前，后面遍历的元素，只要找到前面比它大的元素，就将自身替换进去。相当于拼接在之前的递增子序列后面，arr的长度就是最小递增子序列的长度，它本身的dp[i]就是替换元素的pos的下标值+1（加自身）
            # 用二分法找到arr中第一个比ele_i大（或相等）的元素的位置
            pos = bisect.bisect_left(arr,l[i])
            arr[pos] = l[i]
            dp[i] = pos + 1
    return dp

n = int(input())
l = list(map(int,input().split()))
dp_l = inc_max(l)
dp_r = inc_max(l[::-1])[::-1]
r = n - max([dp_l[i]+dp_r[i]-1 for i in range(n)]) #相加并减去重复计算(自身被加了2次，需要减1)
print(r)