题解 | #合唱队#

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] Q = new int[n];
            for (int i = 0; i < n; i++) {
                Q[i] = sc.nextInt();
            }

            //填左侧动态规划表
            Main m4 = new Main();
            int[] resl = m4.DTGHtable(Q);

            //队列倒置后，填右侧动态规划表
            int[] Q0 = Arrays.copyOf(Q, Q.length);
            for (int j = 0; j < Q0.length; j++) {
                Q0[j] = Q[Q.length - 1 - j];
            };

            int[] resr = m4.DTGHtable(Q0);

            
            //左侧结果+右侧结果+1，排序后取最大值，输出（总人数-这个最大值）
            int[] res = new int[Q.length];
            for (int i = 0; i < res.length; i++) {
                res[i] = resl[i + 1] + resr[resr.length - 1 - i] + 1;
            }
            Arrays.sort(res);
            System.out.println(n - res[res.length - 1]);
        }
    }

    //填动态规划表的方法
    public int[] DTGHtable(int T[]) {
        int n = T.length;
        int[][] table = new int[n + 1][n + 1];
        int[] Ti = Arrays.copyOf(T, n);

        //首行首列设为0
        for (int i = 0; i < n + 1; i++) {
            table[i][0] = 0;
        }
        for (int j = 0; j < n + 1; j++) {
            table[0][j] = 0;
        }
        //从第1列1行开始填
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (i < j && Ti[i - 1] < T[j - 1]) {//合适时的取值公式
                    table[i][j] = Math.max(1 + table[i - 1][i], table[i - 1][j]);
                } else if ((i >= j) || (Ti[i - 1] >= T[j - 1])) {//不合适时的取值公式
                    table[i][j] = table[i - 1][j];
                }
            }
        }
        return table[table.length-1];
    }
}