题解 | #合唱队#转换成最长递增自序列 LCS

import java.math.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.stream.*;
import java.util.regex.*;
import java.util.function.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();
        int[] a = new int[count];
        for (int i = 0; i < count; i++) {
            a[i] = in.nextInt();
        }
        // lcs
        final int[] d1 = lis(a);
        final int[] d2 = lds(a);

        int max = IntStream.range(0, count)
                  .mapToObj(i->d1[i] + d2[i] - 1)
                  .max(Integer::compare).get();

        System.out.println(count - max);
    }

    static int[] lis(int[] a) {
        int[] d = new int[a.length];
        Arrays.fill(d, 1);
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < i; j++) {
                if (a[i] > a[j]) {
                    d[i] = Math.max(d[i], d[j] + 1);
                }
            }
        }
        return d;
    }

    static int[] lds(int[] a) {
        int[] d = new int[a.length];
        Arrays.fill(d, 1);
        for (int i = a.length - 1; i >= 0 ; i--) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {
                    d[i] = Math.max(d[i], d[j] + 1);
                }
            }
        }
        return d;
    }
}