题解 | #合唱队#

import java.io.*;

public class Main{

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str;
    while((str = br.readLine()) != null) {
        int n = Integer.parseInt(str);
        String[] ss = br.readLine().split(" ");
        int[] arr = new int[ss.length];
        for(int i = 0; i < ss.length; i++) {
            arr[i] = Integer.parseInt(ss[i]);
        }
        // 最长递增子序列
        int[] dp = new int[ss.length];
        for(int i = 0; i < ss.length; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(arr[i] > arr[j] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
            }
        }

        // 反转数列，求以第i个元素开头的最长下降子序列即
        // 求反转数列的以第i个元素结尾的最长递增子序列
        
        int[] reverse = new int[arr.length];
        for(int i = arr.length - 1; i > -1; i--) {
            reverse[arr.length - i - 1] = arr[i];
        }
        // 反转数列最长递增子序列
        int[] dp1 = new int[ss.length];
        for(int i = 0; i < ss.length; i++) {
            dp1[i] = 1;
            for(int j = 0; j < i; j++) {
                if(reverse[i] > reverse[j] && dp1[j] + 1 > dp1[i]) dp1[i] = dp1[j] + 1;
            }
        }

        int res = 3000;
        for(int k = 2; k < ss.length - 2; k++) {
            int left = dp[k];
            int right = dp1[ss.length - 1 - k];    // dp也要反转
            res = Math.min(res, ss.length + 1 - left - right);
        }
        System.out.println(res);
    }
}

}