package Acwing算法练习.第五章dp;

import java.util.Scanner;
//每次通过二分找到小于a[i]的最大的数的位置，并将a[i]接在后面
//进来一个数a[i]时，通过二分在q[]中找到最大的小于ai的数，就能够将ai接到该数的后面，即更新q[r + 1] = a[i]
public class 最长上升子序列优化 {
    static int N = 100010;
    static int[] a = new int[N];
    static int[] q = new int[N];//使用q[]存储所有不同长度的上升子序列结尾的最小值
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0;i<n;i++) a[i] = sc.nextInt();
        q[0] = Integer.MIN_VALUE;
        int len = 0;
        for(int i=0;i<n;i++){
            int l = 0,r = len;
            while(l<r)
            {
                int mid = l+r+1>>1;
                if(q[mid]<a[i]) l = mid;
                else r = mid-1;
            }
            len = Math.max(len,r+1);
            q[r+1] = a[i];
        }
        System.out.println(len);
    }

}