题解 | #合唱队#

// 找先递增再递减的最长子序列

// 所以就先从左到右找一遍最长递增子序列

// 再从右往左找一遍递增子序列

// 然后我们将两者对应的位置相加再减1 就是先递增再递减的子序列， 然后求一下max,

// 最后n-max即为我们要求的最小出队人数

#include <bits/stdc++.h>
using namespace std;

// 找先递增再递减的最长子序列
// 所以就先从左到右找一遍最长递增子序列
// 再从右往左找一遍递增子序列
// 然后我们将两者对应的位置相加再减1 就是先递增再递减的子序列， 然后求一下max, 
// 最后n-max即为我们要求的最小出队人数

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> dp1(n);
    vector<int> dp2(n);
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    
    for(int i = 0; i < n; i++)
    {
        dp1[i] = 1;
        for(int j = 0; j < i; j++)
        {
            if(arr[i] > arr[j] && dp1[i] < dp1[j]+1)
                dp1[i] = dp1[j] + 1;
        }
    }
    reverse(arr.begin(), arr.end());
    for(int i =0; i < n; i++)
    {
        dp2[i] = 1;
        for(int j = 0; j < i; j++)
        {
            if(arr[i] > arr[j] && dp2[i] < dp2[j]+1)
                dp2[i] = dp2[j] +1;
        }
    }
    int maxn = -1;
    // reverse(dp2.begin(), dp2.end()); 
    // 这说明不反转也是可以的，直接dp2[n-i-1] 计算即可
    for(int i = 0; i < n; i++)
    {
        maxn = max(maxn, dp1[i]+ dp2[n-i-1]-1);
    }

    cout << n- maxn << endl;



}
// 64 位输出请用 printf("%lld")