题解 | #合唱队#复杂度O(N)，最大前缀和最大后缀

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size = Integer.parseInt(in.nextLine());
        String input = in.nextLine();
        String[] split = input.split(" ");
        int[] heights = new int[size];
        for (int i = 0; i < size; i++) {
            heights[i] = Integer.parseInt(split[i]);
        }

        // 正向统计最大增长队列长度
        int[] maxQueue = new int[size];
        Arrays.fill(maxQueue, 1);
        for (int i = 1; i < size; i++) {
            int max = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (heights[i] > heights[j] && maxQueue[j] > max) {
                    maxQueue[i] = maxQueue[j] + 1;
                    max = maxQueue[j];
//                    break;
                }
            }
        }

        // 反向统计最大增长队列长度
        int[] maxQueueReversed = new int[size];
        Arrays.fill(maxQueueReversed, 1);
        for (int i = size - 2; i >= 0; i--) {
            int max = 0;
            for (int j = i + 1; j <= size - 1; j++) {
                if (heights[i] > heights[j] && maxQueueReversed[j] > max) {
                    maxQueueReversed[i] = maxQueueReversed[j] + 1;
                    max = maxQueueReversed[j];
//                    break;
                }
            }
        }

        // 合并统计结果，算出构建最长合唱队需要剔出的人数
        int maxLength = 0;
        for (int i = 0; i < size; i++) {
            maxQueue[i] = (maxQueue[i] + maxQueueReversed[i] - 1);
            maxLength = Math.max(maxLength, maxQueue[i]);
        }
        System.out.println(size - maxLength);
    }
}