合唱队

描述	计算最少出列多少位同学，使得剩下的同学排成合唱队形 说明： N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。  合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，   则他们的身高满足存在i（1<=i<=K）使得Ti<T2<......<Ti-1<Ti>Ti+1>......>TK。       你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
知识点	循环
运行时间限制	0M
内存限制	0
输入	整数N 一行整数，空格隔开，N位同学身高
输出	最少需要几位同学出列
样例输入	8 186 186 150 200 160 130 197 200
样例输出	4

/*解题思路： 
首先分别求出每一个元素对应的最长递增子序列和最长递减子序列 
然后将对应的最长递增子序列长度和最长递减子序列长度对应相加，找到最大的一个。 
最后用总的人数减去最大的这个和，由于多减了1，再加上即可。 */

import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner scanner=new Scanner(System.in);
        int N=scanner.nextInt();
        int[] height=new int[N];
        for (int i = 0; i < N; i++) {
            height[i]=scanner.nextInt();
        }
        Main main=new Main();
        int[] arrayLenUp=main.getLISUp(height);
        int[] arrayLenDown=main.getLISDown(height);
        int total=2;
        int temp;
        for (int i = 0; i < N; i++) { //对应求和找到最大的那个
            temp=arrayLenUp[i]+arrayLenDown[N-1-i];
            if (temp>total) {
                total=temp;
            }
        }
        System.out.println((N-total+1)); //输出最终结果
        scanner.close();

    }

    public int binarySearchPosition(int arrayOut[],int left,int right,int key){ //二分查找要替换的位置

        int mid;

        if (arrayOut[right]<key) {
            return right+1;
        }else {
            while(left<right){
                mid=(left+right)>>>1;
                if (arrayOut[mid]<key) {
                    left=mid+1;
                }else {
                    right=mid;
                }       
            }
                return left;
        }

    }

    public int[] getLISUp(int[] arrayIn){ //获取最长递增子序列并把它们保存在数组arrayLen中

        int len=1;
        int position;
        int[] arrayOut=new int[arrayIn.length+1];
        arrayOut[1]=arrayIn[0];
        int[] arrayLen=new int[arrayIn.length];
        arrayLen[0]=1;
        for (int i = 1; i < arrayIn.length; i++) {
            position=binarySearchPosition(arrayOut, 1, len, arrayIn[i]);
            arrayOut[position]=arrayIn[i];
            if (position>len) {
                len=position;
            }
            arrayLen[i]=position;
        }
        return arrayLen;
    }

    public int[] getLISDown(int[] arrayIn){ ////获取最长递减子序列并把它们保存在数组arrayLen中
        int[] arrayReverse=new int[arrayIn.length];
        int[] arrayLen=new int[arrayIn.length];
        for (int i = 0; i < arrayReverse.length; i++) { //将最长递减子序列问题转换为最长递增子序列问题
            arrayReverse[i]=arrayIn[arrayIn.length-1-i];
        }
        arrayLen=getLISUp(arrayReverse);
        return arrayLen;
    }

}