题解 | #合唱队#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // list保存数据
        int n = in.nextInt();
        int[] list = new int[n];
        for (int i = 0; i < n; i++) {
            list[i] = in.nextInt();
        }
        // dp1[3] 表示如果让list[0]~list[3]保持递增需要删除的元素的个数
        // dp[0] = 0
        // 如何计算dp[i]？(i从1到最后)
        // 用j 遍历list[0]到list[i-1]
        // 如果list[j]小于dp[i]，计算tempDpI = dp[j] + i - j - 1
        // 否则，计算tempDpI = j + 1
        int[] dp1 = new int[n];
        dp1[0] = 0;
        for (int i = 1; i < n; i++) {
            int res = n;
            for (int j = 0; j < i; j++) {
                if (list[j] < list[i]) {
                    res = Math.min(res, dp1[j] + i - j - 1);
                } else {
                    res = Math.min(res, i);
                }
            }
            dp1[i] = res;
        }
        
        // dp2[3] 表示如果让list[3]~list最后一个元素 保持递增需要删除的元素的个数
        // 可以看出dp2就相当于把上面的步骤中，list和dp1调转
        int[] dp2 = new int[n];
        dp2[n-1] = 0;
        for (int i = n-2; i >= 0; i--) {
            int res = n;
            for (int j = n-1; j > i; j--) {
                if (list[j] < list[i]) {
                    res = Math.min(res, dp2[j] + j - i - 1);
                } else {
                    res = Math.min(res, n-i-1);
                }
            }
            dp2[i] = res;
        } 

        // 计算dp1[i] + dp2[i]的最小值
        int res = n;
        for (int i = 0; i < n; i++) {
            res = Math.min(res, dp1[i] + dp2[i]);
        }
        System.out.println(res);
    }
}