题解 | #合唱队#

import java.util.Scanner;
/**
动态规划 

 确定i的位置
 从左向右找递增子串，
 从右向左找递增子串
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = in.nextInt();
        }
        int[] left = new int[n];
        int[] right = new int[n];
        //求i位置左侧最长递增子串, 最大 < arr[i]
        for(int i = 0; i < n; i++){
            left[i] = 1; //最小为1
            //遍历求最长子串
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j]){
                    left[i] = Math.max(left[i], left[j] + 1); // left[j]为当前最长子串，1 为arr[i]本身
                }
            }
        }

        //求i位置右侧最长递减子串，最大 < arr[i]
        for(int i = n-1; i >=0; i--){
            right[i] = 1;
            for(int j = n-1; j > i; j--){
                if(arr[i] > arr[j]){
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }

        //合并求最长合唱团
        int count = 0;
        for(int i = 0; i < n; i++){
            count = Math.max(count, left[i]+ right[i]);
        }
    
        System.out.println(n - count + 1);
    }
}