题解 | #合唱队#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(int a,int b){
    return a>b;
}

int main() {
    int n;
    
    cin>> n;
    vector<int>a(n+1,0);
    for(int i=1;i<=n;i++){
        cin>> a[i];
    }
    vector<vector<int>>vec(n+1,vector<int>(2,1));

    for(int i=1;i<=n;i++){
        for(int left=1;left<=i;left++){
            if(a[left]<a[i])vec[i][0]=max(vec[i][0],vec[left][0]+1);
        }
    }

    for(int i=n;i>=1;i--){
        for(int right=n;right>=i;right--){
            if(a[right]<a[i]){
                vec[i][1]=max(vec[i][1],vec[right][1]+1);
            }
        }
    }

    vector<int>res(n+1,0);
    for(int i=1;i<=n;i++){
        if(vec[i][0]!=0&&vec[i][1]!=0){
            res[i]=vec[i][0]+vec[i][1]-1;
        }
    }
    sort(res.begin(),res.end(),cmp);
    cout<<n-res[0]<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")