题解 | #合唱队#

public class Main {
    public static void main(String[] argss){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
            int n=sc.nextInt();
            int[] talls=new int[n];
            for(int i=0;i<n;i++){
                talls[i]=sc.nextInt();
            }
            int[] left=new int[n];
            int[] right=new int[n];
            left[0]=1;
            right[n-1]=1;
//             System.out.print(talls[n-1]);
            //数组各元素最长递增子序列
            for(int i=0;i<n;i++){
                //起始先置1，即元素本身
                left[i]=1;
                for(int j=0;j<i;j++){
                    if(talls[j]<talls[i]){
                        left[i]=Math.max(left[i],left[j]+1);
                    }
                }
            }
            //数组各元素最长递减子序列
            for(int i=n-1;i>=0;i--){
                right[i]=1;
                for(int j=n-1;j>i;j--){
                    if(talls[j]<talls[i]){
                        right[i]=Math.max(right[i],right[j]+1);
                    }
                }
            }
            //数组各元素最长左增右减子序列
            for(int i=0;i<n;i++){
                talls[i]=left[i]+right[i]-1;
            }
            //找到最大值max
            int max=0;
            for(int i:talls){
                if(max<i){
                    max=i;
                }
            }
            System.out.println(n-max);
            
        }
    }       
}