题解 | #合唱队#

import java.util.Scanner;

// 问题可以转换成最长递增/递减子序列问题， 二分查找使查找的时间效率从O(N)
// 降为O(logN) 
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[] heights = new int[N];
            for (int i = 0; i < N; i++) {
                heights[i] = in.nextInt();
            }
            System.out.println(pick(heights));
        }
    }

    public static int pick(int[] h) {
        int n = h.length, out = n;
        for (int i = 0; i < n; i++) {
            int l_len = count(h, 0, i, true);
            int r_len = count(h, i, n - 1, false);
            out = Math.min(out, n - (l_len + r_len - 1));
        }
        return out;
    }

    //获取某个人左边的最长递增身高序列，或右边的最长递减身高序列
    //这里用 二分提高查找效率
    public static int count(int[] h, int left, int right, boolean isUp) {
        int res = 0;
        int[] tail = new int[right - left + 1];
        for (int i = left; i <= right; i++) {
            int l = 0, r = res;
            while (l < r) {
                int mid = (r + l) / 2;
                if (isUp) {
                    if (tail[mid] < h[i]) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                } else {
                    if (tail[mid] > h[i]) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
            }
            if (l == res) {
                res++;
            }
            tail[l] = h[i];
        }
        return res;
    }
}