题解 | #合唱队#

import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            int count = Integer.valueOf(br.readLine());
            String[] str = br.readLine().split(" ");
            int[] dp1 = new int[count + 1];
            int[] dp2 = new int[count + 1];
            int max1 = 0;
            int max2 = 0;
            for (int i = 1; i <= count; i++) {
                dp1[i] = 1;
                for (int j = 1; j < i; j++) {
                    if (Integer.valueOf(str[i - 1]) > Integer.valueOf(str[j - 1])) {
                        dp1[i] = Math.max(dp1[i], dp1[j] + 1);
                    }
                }
                max1 = Math.max(dp1[i], max1);
            }
            for (int i = count; i >= 1; i--) {
                dp2[i] = 1;
                for (int j = count; j > i; j--) {
                    if (Integer.valueOf(str[i - 1]) > Integer.valueOf(str[j - 1])) {
                        dp2[i] = Math.max(dp2[i], dp2[j] + 1);
                    }
                }
                max2 = Math.max(dp2[i], max2);
            }
            int max3 = 0;
            for (int i = 1; i <= count; i++) {
                max3 = Math.max(dp1[i] + dp2[i] - 1, max3);
            }
            System.out.println(count - max3);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}