题解 | #合唱队#

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int N =in.nextInt();
            int[] arr=new int[N];
            for(int i=0;i<N;i++){
                arr[i]=in.nextInt();
            }
            //以中间某元素i作为递增子序列的结尾，递减（反向递增）子序列的结尾
            int[] dp1=new int[N];//dp1[i]表示以i为结尾时的递增子序列长度
            int[] dp2=new int[N];
            //dp每个元素初始化为1，因为任何元素为结尾时，最短的子序列长度都是它自己，长度为1
            Arrays.fill(dp1,1);
            Arrays.fill(dp2,1);
            //从左往右正向递增最长子序列
            for(int i=0;i<N;i++){
                for(int j=0;j<i/*这里j不能=i,不然就是自己和自己比较*/;j++){
                    if(arr[i]>arr[j]){
                       //当第i个元素大于第j个元素时，那第i个元素就可以排入已经排好的j序列中，并排在j之后。
                        //那i排进去了，就可以比j序列的长度多1，即多了第i个元素
                        dp1[i]=Math.max(dp1[i],dp1[j]+1);
                    }
                }
            }
            //递减序列同理，只不过反向递增
            for(int i=N-1;i>0;i--){
                for(int j=N-1;j>i/*这里j不能=i,不然就是自己和自己比较*/;j--){
                    if(arr[i]>arr[j]){
                       //当第i个元素大于第j个元素时，那第i个元素就可以排入已经排好的j序列中，并排在j之后。
                        //那i排进去了，就可以比j序列的长度多1，即多了第i个元素
                        dp2[i]=Math.max(dp2[i],dp2[j]+1);
                    }
                }
            }
            //找到一个位置n,使得左边的递增序列加右边的递减序列长度之和最大
            int[] result = new int[N];
            int ret=1;
            for(int i=0;i<N;i++){
                result[i]=dp1[i]+dp2[i]-1;//减去第i个多加的元素
                ret=Math.max(result[i],ret);
            }
            System.out.println(N-ret);
        }
    }
}