题解 | 合唱队形

def hechang(s, n):
    m = 0
    dp1 = [1]*n
    dp2 = [1]*n
    # dp1[0] = 1
    # dp2[0] = 1
    for i in range(1, n):
        for j in range(0, i):
            if s[i] > s[j]:
                dp1[i] = max(dp1[i], dp1[j]+1)
    for i in range(n-2, -1, -1):
        for j in range(n-1, i, -1):
            if s[i] > s[j]:
                dp2[i] = max(dp2[i], dp2[j]+1)
    for i in range(n):
        a = dp2[i] + dp1[i]
        m = max(a, m)
    return n - m + 1
n = int(input())
s = list(map(int, input().split()))
print(hechang(s, n))