题解 | #合唱队#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++){
            nums[i] = in.nextInt();
        }
        
        int[] dp_left = new int[n];
        Arrays.fill(dp_left,1);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    dp_left[i] = Math.max(dp_left[i],dp_left[j] + 1);
                }
            }
        }

        int[] dp_right = new int[n];
        Arrays.fill(dp_right,1);
        for(int i = n - 1; i >= 0; i--){
            for(int j = n - 1; j > i;j--){
                if(nums[i] > nums[j]){
                    dp_right[i] = Math.max(dp_right[i],dp_right[j] + 1);
                }
            }
        }

        int max = 0;
        for(int i = 0; i < n; i++){
            int len = dp_left[i] + dp_right[i] - 1;
            max = Math.max(max,len);
        }

        System.out.println(n - max);
    }
}