[//]: # 这个题目就是顺着求一遍最长上升子序列，再倒着求一遍最长上升子序列，然后求求最大值就是答案了。这里可以用java自己带的数组的二分查找方法

java 代码

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N=102;
    static int n;
    public static void main(String[] args) throws Exception{

      //  System.setIn(new FileInputStream("E:\\data\\p1091.txt"));
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        n=Integer.parseInt(st.nextToken());
        st=new StringTokenizer(br.readLine());
        Integer a[] = new Integer[n];
        for(int i=0;i<n;i++){
            a[i]=Integer.parseInt(st.nextToken());
        }
          if(n==2){
              System.out.println(1);
          } else {
              solve(a,n);
          }
    }

    private static void solve(Integer[] A,int len){
        int dp1[]=doDP(A,len);
        Collections.reverse(Arrays.asList(A));
        int dp2[]=doDP(A,len);
        int res=len;
        for(int i=0;i<len;i++){
            res=Math.min(res,len-(dp1[i]+dp2[len-i-1]-1));
        }
        System.out.println(res);
    }

//用二分法求最长上升子序列
    private static int [] doDP(Integer[] A,int len){
      int res[]=new int[len];
      int up[]=new int[len];
      int top=0;
      res[0]=top+1;
      up[0]=A[0];
      for(int i=0;i<len;i++){
          int idx=Arrays.binarySearch(up,0,top+1,A[i]);
          //这里是找到了新的位置
          if(idx<0){
              idx=-idx-1;
          }
          if(idx>top){//这里找到新的位置了，需要记录当下最长的子序列的长度需要加1
              top++;
          }
          up[idx]=A[i];//这里就是将新的值更新到记录最长上升子序列的数组中，新的添加到数组后面，有比更小的则替换掉以前的
          res[i]=top+1;//已当前节点结尾的最长上升子序列的长度
      }

      return res;
    }

}