题解 | #合唱队#

n = int(input())
i = input().split()
i = list(map(int, i))
zuo = [0]
you = [0]
for h in range(1, n):
    jilu = []
    for k in range(h):
        if i[h] > i[k]:
            jilu.append(zuo[k])
    if len(jilu) == 0:
        zuo.append(0)
    else:
        zuo.append(max(jilu) + 1)
i=i[::-1]
for h in range(1, n):
    jilu = []
    for k in range(h):
        if i[h] > i[k]:
            jilu.append(you[k])
    if len(jilu) == 0:
        you.append(0)
    else:
        you.append(max(jilu) + 1)
you=you[::-1]
he=[]
for a in range(n):
    if zuo[a]>0 and you[a]>0:
        he.append(zuo[a]+you[a])
q=max(he)
print(n-q-1)

题目可以等价为求最长的合唱队形的长度，那么我们可以求出每一个人作为中间人时合唱队形长度的最大值，然后再取最大值就行了。

对于第i个人，我们记他左边的合唱队形最长为zuo[i],则有zuo[i]=zuo[k]+1，其中，k是i左边比i矮的人中，zuo[k]值最大的人。

依据这个公式我们就可以从推出所有人的“左合唱队形"的最大值,同理可以求出”右合唱队形“的最大值，两者相加再+1即为最长的合唱队形。