题解 | #合唱队#

import java.util.ArrayList; import java.util.List; import java.util.Scanner;

public class Main{

private static void InitList(Integer[] list,int size){
    for (int i =0;i<size ;i++){
        list[i]=1;
    }
}

public static void main(String[] args) {



    int num = 0;

    List<Integer> list_height = new ArrayList<Integer>();

    Scanner sc = new Scanner(System.in);

    num = sc.nextInt();


    int max_seq=0;
    while(num>0){
        list_height.add(sc.nextInt());
        num--;
    }


    max_seq= getSeq(list_height,list_height.size());



    System.out.println(list_height.size()-max_seq+1);



}

// flag_lr: false --> left
//          true  --> right

public static int getSeq( List<Integer> heights ,int num ){

    Integer[] list_left = new Integer[num];
    Integer[] list_right = new Integer[num];
    InitList(list_left,num);
    InitList(list_right,num );

    int max_seq = 1;


        //查询右侧子序列
        for (int j =num-2 ; j>=0;j--){
            for (int k = j+1; k<=num-1 ;k++){
                if (heights.get(k)<heights.get(j)) {
                    list_right[j]=Math.max(list_right[j],list_right[k]+1);
                }
            }
        }

        //遍历左侧子序列

        for (int j =1 ; j<num;j++){
            for (int k = j-1 ;k>=0 ; k--){

                if (heights.get(k)<heights.get(j)){

                    list_left[j] = Math.max(list_left[j] ,list_left[k] +1);

                }

            }
        }







    for (int n = 0; n < list_right.length; n++) {
        max_seq = max_seq < list_right[n]+list_left[n]? list_right[n]+list_left[n]:max_seq;
    }
    return max_seq;
}

}