题解 | #合唱队形#

考虑分别以各个位置为中心折点，在每个位置求其：

1. 之前的最长严格上升子序列长度（要求包括自己）：实际就是题目DP14中dp数组
2. 之后的最长严格下降子序列长度（要求包括自己）：可通过两次数组反转得到

然后就是简单的加减法，得到以各个位置为中心折点时，最少要Out的人数，取最小

def maxIncSub(arr):
    # @arr 传入数组
    # @return 返回求最长严格上升子序列的长度的dp数组
    n=len(arr)
    dp=[1]*n
    for i in range(1,n):
        for j in range(i):
            if arr[j]<arr[i]:
                dp[i]=max(dp[i],dp[j]+1)
    return dp

n=eval(input())
arr=list(map(int,input().split()))

dp1=maxIncSub(arr)

arr.reverse()
dp2=maxIncSub(arr)
dp2.reverse()

minOut=n-1
for i in range(0,n):
    Out=(i+1)-dp1[i]+(n-i)-dp2[i]
    minOut=min(minOut,Out)  
print(minOut)