题解 | #合唱队#

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int total = in.nextInt();
        int[] lengths = new int[total];
        // 从左遍历得到的最长递增子序列长度集合
        int[] left = new int[total];
        // 从右遍历得到的最长递增子序列长度集合
        int[] right = new int[total];
        for (int i = 0; i < total; i++) {
            lengths[i] = in.nextInt();
        }

        // 初始化两个集合
        left[0] = 1;
        right[total - 1] = 1;

        for (int i = 1; i < total; i++) {
            left[i] = 1;
            // 动态规划的部分，运用前面的最优部分得到后面的最优解
            for (int j = 0; j < i; j++) {
                // 如果当前的第i个元素比其前面遍历到的第j个元素大, 则让left[j]增大
                // 要不用之前的最优值left[i]
                // 要不就用自身+1 - left[j] + 1
                if (lengths[i] > lengths[j]) {
                    left[i] = Math.max(left[i], left[j] + 1);
                }
            }
        }

        for (int i = total - 1; i > 0; i--) {
            right[i] = 1;
            // 动态规划的部分，运用前面的最优部分得到后面的最优解
            for (int j = total - 1; j > i; j--) {
                // 如果当前的第i个元素比其后面遍历到的第j个元素大, 则让right[j]增大
                // 要不用之前的最优值left[i]
                // 要不就用自身+1 - left[j] + 1
                if (lengths[i] > lengths[j]) {
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }

        // 计算该位置左边递增长度+右边递减长度，从而得出合唱队最长长度
        int[] chorus = new int[total];
        // 获取到最长的合唱队长度
        int maxLength = 1;
        for (int i = 0; i < total; i++) {
            // 排除自身重复的一次
            // 如[186, 200, 200, 160, 130]
            chorus[i] = left[i] + right[i] - 1;
            maxLength = Math.max(maxLength, chorus[i]);
        }
        // 得出需要去掉几个人
        // 由于不要求最高同学左右人数必须相等，则最大值maxLength可以在数组的最两侧
        System.out.println(total - maxLength);

    }
}