题解 | #合唱队#

参考了高赞的回答，为了加深自己的理解，手撸了一遍二分查找的代码。总的来说还是要自己敲一遍，一行行理解的快一些。

#二分查找，其中ls是从左到右升序
def find_pos(ls, num,start = 0, end = None):
    if end == None:
        end = len(ls)
    while start < end:
        index = (start+end)//2
        if ls[index]<num:
            start = index+1
        else:
            end = index
    return start

def dplist(raw_list):
    dp = [1]*len(raw_list)
    stu_list = [raw_list[0]]
    for i in range(1,len(raw_list)):
        if raw_list[i] > stu_list[-1]:
            stu_list.append(raw_list[i])
            dp[i] = len(stu_list)
        else:
            index = find_pos(stu_list,raw_list[i])
            stu_list[index] = raw_list[i]
            dp[i] = index+1
    return dp

while True:
    try:
        num =int(input()) 
        ls = list(map(int,input().split()))
        l_ls = dplist(ls)
        r_ls = dplist(ls[::-1])[::-1]
        total_ls = [l_ls[i]+r_ls[i]-1 for i in range(len(ls))]
        print(num-max(total_ls))
    except EOFError:
        break