题解 | #合唱队#

import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();

            int[] inputAllNum = new int[n];
            int[] groupNum = new int[n];

            if (n <= 1) { //如果只输入了一个数字则
                System.out.println(0);
            }
            for (int i = 0; i < n ; ++i) {
                inputAllNum[i] = in.nextInt();
            }


            int[] left = new int[n];
            int[] right = new int[n];
            int[] cnt = new int[n];

            left[0] = inputAllNum[0];
            // 左侧计算子序列个数
            int index = 1; 
            for (int i = 0; i < n ; i++) {

                if (inputAllNum[i] > left[index - 1]) {
                    cnt[i] = index;
                    left[index++] =  inputAllNum[i];
                } else {

                    int l = 0, r = index - 1;
                    while (l < r) {
                        int mid = l + (r - l) / 2;
                        if (left[mid] < inputAllNum[i]) {
                            l = mid + 1;
                        } else {
                            r = mid;
                        }
                    }

                    left[l] = inputAllNum[i];
                    cnt[i] = l;  
                }

            }

            right[0] = inputAllNum[n - 1];
            // 右侧计算子序列个数
            index = 1; 
            for (int i = n-2; i >= 0 ; i--) {

                if (inputAllNum[i] > right[index - 1]) {
                    cnt[i] += index;
                    right[index++] =  inputAllNum[i];
                } else {

                    int l = 0, r = index - 1;
                    while (l < r) {
                        int mid = l + (r - l) / 2;
                        if (right[mid] < inputAllNum[i]) {
                            l = mid + 1;
                        } else {
                            r = mid;
                        }
                    }

                    right[l] = inputAllNum[i];
                    cnt[i] += l;  
                }

            }

            int max = 1;
            for(int num : cnt){
                 if( max < num){
                     max = num;
                 }

            }
             System.out.println(n - max -1);




        }
    }

    private static int MaxGoup(int[] h, int[] copyh) {

        int cut = 0;
        int gMax = Integer.MIN_VALUE;

        for (int i = 0 ; i < h.length ; ++i) {

            gMax = Math.max(gMax, h[i]);
            if (gMax == copyh[i]) {
                cut ++;
            }

        }

        return cut;

    }


}