题解 | #合唱队#

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] stu = new int[n];
            for (int i = 0; i < n; i++) {
                stu[i] = sc.nextInt();
            }
            int[] dp = new int[n];
            int[] dpLeft = new int[n];
            int[] dpRight = new int[n];
            for (int i = 0; i < n; i++) {
                dpLeft[i] = 1;
                for (int j = 0; j < i; j++) {
                    if(stu[i] > stu[j]){
                        dpLeft[i] = Math.max(dpLeft[i], dpLeft[j] + 1);
                    }
                }
            }
            for (int i = n - 1; i >= 0; i--) {
                dpRight[i] = 1;
                for (int j = n - 1; j > i; j--) {
                    if(stu[i] > stu[j]){
                        dpRight[i] = Math.max(dpRight[i], dpRight[j] + 1);
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                dp[i] = dpLeft[i] + dpRight[i] - 1;
            }
            int max = 1;
            for (int i = 0; i < n; i++) {
                max = Math.max(dp[i], max);
            }
            System.out.println(n - max);
        }
    }
}