题解 | #合唱队#

import sys
num = int(input())
heights = list(map(int, input().split()))
resmax = 0
def halpsearch(buffs,key):
    l,r=0,len(buffs)-1
    mid=l
    while(l<r):
        mid=(l+r)//2
        if(buffs[mid]>=key):
            r=mid
        else:
            l=mid+1
    return r
def solve(heights):
    dp = [1] * len(heights)
    bufsorted=[]
    bufsorted.append(heights[0])
    for i in range(1,num):
        if(heights[i]>bufsorted[-1]):
            bufsorted.append(heights[i])
            dp[i]=len(bufsorted)
        elif(heights[i]<bufsorted[0]):
            bufsorted[0]=heights[i]
        else:
            index=halpsearch(bufsorted,heights[i])
            bufsorted[index]=heights[i]
            dp[i]=index+1
    return dp
dp1=solve(heights)
dp2=solve(heights[::-1])[::-1]
for i in range(num):
    if (dp1[i] + dp2[i] - 1) > resmax:
        resmax = dp1[i] + dp2[i] - 1
print(num - resmax)

简洁版