这是【最长递增子序列】的衍生问题

合唱队由一个最长递增子序列和一个最长递减子序列拼接而成，中间的最高元素会重复，拼接时要减去1

dp1[i]表示以s1[i]结尾的最长递增子序列的长度

递减子序列可以把原列表倒序之后继续用递增子序列的逻辑处理，处理完成得到dp2之后再倒序即可

最后把dp1和dp2各项对应相加，取其中的最大值即可

注：时间复杂度为O(n^2)，有时候只能过19/20

a=int(input())
s1=[int(i) for i in input().split()]
#dp1【i】表示以s1【i】结尾的递增子序列的长度
dp1=[1]*len(s1)#初始化dp1数组
#dp2【i】表示以s1【i】结尾的递减子序列的长度
dp2=[1]*len(s1)#初始化dp2数组
#对dp1打表
for i in range(1,len(dp1)):#遍历dp1数组
    for j in range(0,i):#遍历dp1【i】前面元素
        if s1[i]>s1[j] and dp1[i]<dp1[j]+1:#条件是s1【i】>s1【j】，可以产生新的递增子序列
            dp1[i]=dp1[j]+1
#递减子序列可以先将数字数组倒转，然后求递增子序列,最后再将dp2倒转即可
#倒转s1,reverse直接操作原列表，没有返回值
s1=s1[::-1]#注意这里用切片，reverse的话慢一些，有可能超时
#对dp2打表
for i in range(len(dp2)-1):#遍历dp2数组0,len(dp2)-1
    for j in range(0,i):#遍历dp2【i】前面元素
        if s1[i]>s1[j] and dp2[i]<dp2[j]+1:#条件是s1【i】>s1【j】，可以产生新的递增子序列
            dp2[i]=dp2[j]+1
#倒转dp2
dp2=dp2[::-1]
#将dp1和dp2合并起来,注意中间元素重合，要减一
dp3=[]
dp3=[dp1[i]+dp2[i]-1 for i in range(len(dp1))]
#这道题问的是最少需要几个同学出列，也就是数组长度 减去 最大可以形成的合唱队长度
print(len(dp3)-max(dp3))