题解 | #合唱队#

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()) { // 注意 while 处理多个 case
            // 获取students
            int n = in.nextInt();
            int[] students = new int[n];
            for (int i = 0; i < n; i++) {
                students[i] = in.nextInt();
            }

            // 使用DP来计算两个数组，
            // 一个是左手边的最长上升子序列长度left,
            // 一个是右手边的最长上升子序列长度right（即最长下降子序列）
            int[] left = new int[n];
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (students[j] < students[i]) {
                        left[i] = Math.max(left[i], left[j] + 1);
                    }
                }
            }
            int[] right = new int[n];
            for (int i = n - 2; i >= 0; i--) {
                for (int j = n - 1; j > i; j--) {
                    if (students[j] < students[i]) {
                        right[i] = Math.max(right[i], right[j] + 1);
                    }
                }
            }
            // 计算当前的最长合唱队形: 最长的上升子序列和下降子序列的长度之和 + 1
            // 另外一个valid的合唱队形要保证左手边和右手边的值都不为空
            int max = 0;
            for (int i = 0; i < n; i++) {
                if (left[i] != 0 && right[i] != 0) {
                    max = Math.max(max, left[i] + right[i] + 1);
                }
            }
            System.out.println(students.length - max);
        }
    }
}