题解 | #合唱队#

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] input = new int[n];
        for (int i = 0; i < n; ++i) {
            input[i] = in.nextInt();
        }
        
        int[] leftMax = new int[input.length];
        Arrays.fill(leftMax, 1);
        int[] rightMax = new int[input.length];
        Arrays.fill(rightMax, 1);

        for (int i = 0; i < input.length; ++i) {
            for (int x = 0; x < i; ++x) {
                if (input[x] < input[i]) 
                    leftMax[i] = Math.max(leftMax[i], leftMax[x] + 1);
            }
        }
        
        for (int j = input.length - 1; j > 0; --j) {
            for (int y = input.length - 1; y > j; --y) {
                if (input[y] < input[j]) 
                    rightMax[j] = Math.max(rightMax[j], rightMax[y] + 1);
            }
        }
        
        int[] max = new int[input.length];
        Arrays.setAll(max, i -> leftMax[i] + rightMax[i]);
        
        System.out.println(n - Arrays.stream(max).max().getAsInt() + 1);
    }
}