题解 | #合唱队#

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while(in.hasNextInt()){
            int num = in.nextInt();
            int[] nums = new int[num];
            for(int i=0 ; i<num ; ++i){
                nums[i] = in.nextInt();
            }
            //动态规划dpl数组用于保存第i个元素（包含自身）的最大上升序列个数
            int[] dpl = new int[num];
            for(int i=0 ; i<num ; ++i){
                dpl[i] = 1;
            }
            for(int i=1 ; i<num ; ++i){
                for(int j=0 ; j<i ; ++j){
                    if(nums[j]<nums[i]){
                        dpl[i] = Math.max(dpl[i], dpl[j]+1);
                    }
                }
            }
            int[] dpr = new int[num];
            for(int i=0 ; i<num ; ++i){
                dpr[i] = 1;
            }
            for(int i=num-2 ; i>=0 ; --i){
                for(int j=num-1 ; j>i ; --j){
                    if(nums[i]>nums[j]){
                        dpr[i] = Math.max(dpr[i], dpr[j]+1);
                    }
                }
            }
            int maxNum = 0;
            for(int i=0 ; i<num ; ++i){
                maxNum = Math.max(maxNum, dpl[i]+dpr[i]-1);
            }

            System.out.println(num-maxNum);
        }
    }
}