题解 | #合唱队#

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        int index = 0;
        while(sc.hasNext()){
            arr[index++] = sc.nextInt();
        }
        int[] arr1 = new int[N+1];
        int[] arr2 = new int[N+1];
        int[] a = new int[N+1];
        int len = 1,len2 = 1;
        arr1[1] = arr[0];
        arr2[1] = arr[N-1];
       for(int i = 1;i<N;i++){
           if(arr1[len] < arr[i]){
               arr1[++len] = arr[i];
           }
           else{
               int lo = 1,hi = len,rec = 0;
               while(hi >= lo){
                   int mid = lo + ((hi-lo)>>1);
                   if(arr1[mid] < arr[i]){
                       lo = mid+1;
                   }
                   else{
                       hi = mid-1;
                   }
               }
               arr1[lo] = arr[i];//更新
           }
           a[i] = len;
       }
      for(int i = N-2;i>=0;i--){
           if(arr2[len2] < arr[i]){
               arr2[++len2] = arr[i];
           }
           else{
               int lo = 1,hi = len2,rec = 0;
               while(hi >= lo){
                   int mid = lo + ((hi-lo)>>1);
                   if(arr2[mid] < arr[i]){
                       lo = mid+1;
                   }
                   else{
                       hi = mid-1;//在相等的情况下右边还是要往后退的，递增
                   }
               }
               arr2[lo] = arr[i];
           }
               a[i] += len2;
       }
        int res = 0;
        for(int num : a){//每个地方都试一下，找出最大的
            res = Math.max(res,num);
        }
        System.out.print(N-res+1);
   }
}