题解 | #合唱队#

import sys
#解决问题的过程为：寻找每个位置左边的最长递增序列和右边的最长递减序列，遍历取最长，即为最长的"合唱队"
def uplongn(lst): #寻找序列中每个位置左边能构成递增序列的最大长度dp(包括自身)
    dp = []   
    for i in range(len(lst)):
        dp.append(1)    ##初始化最长序列长度为1
        for j in range(i):  
		#对每个位置i，从0到i位置遍历：如果i位置高于j位置，则dp[i]应该比dp[j]大1同时也应该比dp[j]大
		#同时注意到，对于任意的i>j，如果i位置高于j位置，都应该有dp[i]比dp[j]+1大，所以不仅需要i遍历，j遍历同样需要。如果单纯计算各位置左侧小于自身的点个数，一旦左侧有极小值时则会计算错误序列长度。
            if lst[i] > lst[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
num = int(input())  ##样本数
lst = list(map(int,input().split(" "))) ##样本，用" "分割
res = []  #初始化结果
dp1 = uplongn(lst) #从左开始向右，截至各点的最长序列长度
dp2 = uplongn(lst[::-1])[::-1]  ##从右开始向左，截至各点最长序列长度
for i in range(num):
    res.append(dp1[i] + dp2[i] -1)  #计算"合唱队"序列长度，由于各点重复计算了1次，所以需要去掉。
print(num-max(res))