题解 | #合唱队#

import java.util.Scanner;

public class Main { public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    String sta = sc.nextLine();
    int count = Integer.valueOf(sta);
    String s = sc.nextLine();
    String[] c = s.split(" ");
    int [] arr = new int [count]; // 存储正序身高
    int [] arrs = new int [count];  // 存储逆序身高
    int [] grdh = new int [count];  // 存储正序身高等级
    int [] grds = new int [count];  // 存储逆序身高等级
    int Max = 0;
    for(int i=0; i<count; i++){
        arr[i] = Integer.valueOf( c[i] );
        int temp = count-1-i;
        arrs[temp] = arr[i];
    }
    for(int i=0; i<count; i++){
        grdh[i] = high(i, grdh , arr);
    }

    for(int i=0; i<count; i++){
        grds[i] = high(i, grds , arrs);
    }

    for(int i=0; i<count; i++){
        int rev = count - i -1;
        int temp = grds[rev] + grdh[i];
        if(Max < temp){
            Max = temp;
        }
    }
    Max = count -Max + 1;

    System.out.println(Max);

}
public static int high(int ren, int [] grdh, int[] arr){
    int hig = arr[ren];
    grdh[ren] = 1;
    int grade = 0;
    for(int i = ren ; i>=0; i--){
        if(arr[i]<hig && grade <= grdh[i]){
            grade = grdh[i]+1;
        }
    }
    if(grade == 0){
        return 1;
    }
    return grade;
}

}