题解 | #合唱队#

以某个点i为中心，计算0~i的最长上升子序列x，然后翻转列表，计算N~i的最长子序列y，则以i点为中心需要出列的人数为N-(x+y-1)，最后取每个点的最小值

def max_up_arr(arr):
    """查找arr中以i为结尾的最大上升子序列长度"""
    dp = [1]  # 默认为1个
    for i in range(1, len(arr)):
        dp.append(max([1] + [dp[j]+1 for j in range(i) if arr[j] < arr[i]]))
    return dp 

def func(n, arr):
    a1 = max_up_arr(arr)
    a2 = max_up_arr(arr[::-1])[::-1]
    print(n-max(i+j-1 for i, j in zip(a1, a2)))

while True:
    try:
        n = int(input())
        arr = list(map(int, input().split()))
        func(n, arr)
    except EOFError: break