题解 | #合唱队#

#include <iostream>

#define fas(i,a,b) for(int i=a;i<b;++i)//[)
#define fdes(i,b,a) for(int i=b;a<=i;--i) //[]

int dp1[3000];
int dp2[3000];
int nums1[3000];
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        fas(i,0,n)
        {
            cin>>nums1[i];
        }
        dp1[0]=dp2[n-1]=1;
        fas(i,1,n)
        {
            int maxv1=1;
            fas(j,0,i)
            {
                if(nums1[j]<nums1[i])
                {
                    maxv1=max(maxv1,dp1[j]+1);
                }
            }
            dp1[i]=maxv1;
        }

        // fas(i,0,n)
        //     cout<<dp1[i]<<" ";
        // cout<<endl;

        fdes(i,n-2,0)
        {
            int maxv1=1;
            fdes(j,n-1,(i+1))
            {
                if(nums1[j]<nums1[i])
                {
                    maxv1=max(maxv1,dp2[j]+1);
                }
            }
            dp2[i]=maxv1;
        }
        // fas(i,0,n)
        //     cout<<dp2[i]<<" ";
        // cout<<endl;

        int maxv1=0;

        fas(i,0,n)
        {
            maxv1=max(dp1[i]+dp2[i]-1,maxv1);
        }
        cout<<n-maxv1;
    }
}