import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i< n; i++) {
            arr[i] = in.nextInt();
        }

        int[] num = new
        int[n]; // 记录从左到右和从右到左递增最长队列长度的加和
        int[] left = new int[n]; // 记录从左到右递增的队列
        int[] right = new int[n]; // 记录从右到左递增的队列

        num[0] = 0;
        left[0] = arr[0];
        right[0] = arr[n - 1];

        int index = 0;
        for (int i = 1; i< n; i++) {
            if (arr[i] >left[index]) {
                left[++index] = arr[i];
                num[i] = index;
            } else {
                int low = 0;
                int high = index;
                // 利用二分查找法找到arr[i]在left[]数组的位置
                while (low< high) {
                    int mid = (low + high) / 2;
                    if (left[mid]< arr[i]) {
                        low = mid + 1;
                    } else {
                        high = mid;
                    }
                }
                num[i] = low;
                left[low] = arr[i];
            }
        }
        int rightIndex = 0;
        for (int j = n - 2; j >= 0; j--) {
            if (arr[j] >right[rightIndex]) {
                right[++rightIndex] = arr[j];
                num[j] += rightIndex;
            } else {
                int low = 0;
                int high = rightIndex;
                while (low< high) {
                    int mid = (low + high) / 2;
                    if (arr[j] >right[mid]) {
                        low = mid + 1;
                    } else {
                        high = mid;
                    }
                }
                num[j] += low;
                right[low] = arr[j];
            }
        }
        int max = 0;
        for (int i = 0; i< n; i ++) {
            max = Math.max(num[i], max);
        }
        // max是num里面的大值，但是此处需要减去最高值本身
        System.out.println(n - max - 1);
    }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

创新互联专注于企业全网整合营销推广、网站重做改版、贺州网站定制设计、自适应品牌网站建设、H5页面制作、商城网站定制开发、集团公司官网建设、外贸营销网站建设、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为贺州等各大城市提供网站开发制作服务。
标题名称：【华为机试java】HJ24合唱队-创新互联
文章转载：http://kswjz.com/article/ccshcd.html