题解 | #合唱队形# Python3 + 简单解释

import sys
# 峰形队列其实是求 0~i的最长严格上升子序列 + i+1 ~0的最长严格下降子序列
# 求最少出列，就是求它俩相加最大

n = int(input())

height = list(map(int,input().strip().split()))

dp1 = [0] * n # dp[i]记录从0到i的最长上升序列
dp2 = [0] * n # dp2[i]记录从i到n的最长下降序列，或者从n到i的最长上升序列

dp1[0], dp2[n-1] = 1, 1

for i in range(1,n):
    max_num = 0
    for j in range(i):
        if height[j] < height[i]:
            max_num = max(max_num, dp1[j])
    dp1[i] = max_num+ 1

for i in range(n-2,-1,-1):
    max_num = 0
    for j in range(n-1,i,-1):
        if height[j] < height[i]:
            max_num = max(max_num, dp2[j])
    dp2[i] = max_num+ 1

res = [v1+v2-1 for v1, v2 in zip(dp1,dp2)]
print(n - max(res))