题解 | #合唱队#

#动态规划（Dynamic Programming）
# import sys
def left_max(l):
    #计算每个人左边出现的最多人数
    N = len(l)
    dp = [1] * N #若左边没有比自己小的数，则为自己本身，所以初始值为1
    for i in range(N):  #从左往右遍历
        for j in range(i):
            if l[j] < l[i] and dp[i] < dp[j] + 1:
                dp[i] = dp[j] + 1
#             if l[j] < l[i]:
#                 dp[i] = max(dp[i],dp[j] + 1)
    return dp

while True:
    try:
        N = int(input())
        nums = list(map(int, input().split()))

        dp1 = left_max(nums)
        dp2 = left_max(nums[::-1])[::-1]
#         print(dp1)#[1, 1, 1, 2, 2, 1, 3, 4]
#         print(dp2)#[3, 3, 2, 3, 2, 1, 1, 1]
        dp3 = [dp1[i] + dp2[i] for i in range(N)]
        #加起来队列的最大值，就是能够站的最大人数
        print(N - max(dp3) + 1)
    except:
#         print(sys.exc_info())
        break