题解 | #合唱队#

#不是二分查找的问题,是需要辅助数组保存之前dp得到的结果
#二分查找在查找那一步进行了简化,但是其实更重要的是换了思路

def  maxInc(height):
    n = len(height)
    dp = [1]*n
    #维护一个虚拟递增序列
    que = [height[0]]
    for i in range(1,n):
        if height[i]>que[-1]:
            que.append(height[i])
            dp[i] = len(que)
        #把新值维护到这个递增序列中它能够大于前面所有值的最大位置
        #1.大于最后值,append 2.大于pos-1,小于下标为pos的值,替换pos
        #que长度为递增子序列的最大长度
        #下标i对应的值为 递增序列能包含i+1个数,长度能达到i+1所需要越过的门槛
        #que中维护的是 一个最低代价的达到各递增序列长度的门槛值
        else:
            pos=0
            while que[pos]<height[i]:
                pos +=1
            que[pos] = height[i]
            dp[i]= pos+1
    return dp   
    
while  True:
    try:
        n = int(input())
        height = list(map(int,input().split()))
        inc = maxInc(height)
        dec = maxInc(height[::-1])[::-1]
        max_len = 0
        for i in range(n):
            if max_len< inc[i]+dec[i]-1:
                max_len= inc[i]+dec[i]-1
        
        print(n-max_len)

    except:
        break