int longestIncreasingSubsequence(vector<int> arr) {
    vector<int> length = {0, arr[0]};
    for (int i=1; i < arr.size(); i++) {
        auto L = lower_bound(length.begin()+1, length.end(), arr[i]);
        if (L != length.end()) *L = arr[i];
        else length.push_back(arr[i]);
    }
    return length.size()-1;
}

//package solve_problems;
/*
 * 2024 ^_^
 *ThinhNguyen97
 * 
 */

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;



public class Solve_problems 
{
   static void solve(int n, int[] array) 
   {
       List<Integer> res=new ArrayList<>();
       res.add(array[0]);
       for (int i = 1; i < n; i++) 
       {
            int pos = Collections.binarySearch(res, array[i]);

            if (pos < 0) {
                // Element not found, calculate the insertion point
                pos = -pos - 1;
                if (pos == res.size())
                    res.add(array[i]);
                else
                    res.set(pos, array[i]);
            }
           // Print the current LIS
//           res.forEach((x) -> {
//               System.out.print(x + " ");
//           });
//            System.out.println();
        }
       // Print the length of the LIS
        System.out.println(res.size());
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Input
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = sc.nextInt();

        // Solve the problem
        solve(n, array);

        // Close the Scanner instance
        sc.close();
    }
}
 

//O(nlogn)
// 
#include <string>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <queue>
using namespace std;
using ll=long long;

//F[i] save the last element min it can obtain of increasing subsequence its length = i 
//dung bs
//lowerbound phan tu dau tien >=a[i]
//in: 9
//1 4 2 3 8 10 6 9 13
//out:6
//ket qua:1 2 3 6 9 13








int main()
{ 
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];

    vector<int> res;
    res.push_back(a[0]);
    for(int i=1;i<n;i++)
    {
        auto it =lower_bound(res.begin(),res.end(),a[i]);
        if(it==res.end())
            res.push_back(a[i]);
        else
            *it=a[i];
        // for(int x:res)
        //     cout<<x<<' ';
        // cout<<endl;
    }
    //cout<<endl;
    cout<<res.size();
}

import java.util.Arrays;
import java.util.Scanner;

public class Solve_problems {

    static void solve(int n, int[] array) {
        int[] tails = new int[n];
        int len = 1;

        tails[0] = array[0];

        for (int i = 1; i < n; i++) {
            if (array[i] < tails[0]) {
                // New smallest value
                tails[0] = array[i];
            } else if (array[i] > tails[len - 1]) {
                // Array[i] extends the largest subsequence
                tails[len++] = array[i];
            } else {
                // Array[i] will become end candidate of an existing
                // subsequence or replace a candidate in the middle
                int pos = Arrays.binarySearch(tails, 0, len, array[i]);
                if (pos < 0) {
                    pos = -pos - 1;
                }
                tails[pos] = array[i];
            }
        }

        System.out.println(len);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Input
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = sc.nextInt();

        // Solve the problem
        solve(n, array);

        // Close the Scanner instance
        sc.close();
    }
}

def binarySearch(arr, low, high, key):
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < key:
            low = mid + 1
        else:
            high = mid - 1
    return low

def longestIncreasingSubsequence(arr):
    n = len(arr)
    lis = [0] * n
    length = 0

    for i in range(n):
        pos = binarySearch(lis, 0, length - 1, arr[i])
        lis[pos] = arr[i]
        if pos == length:
            length += 1

    return length

# Reading input
n = int(input())
arr = [int(input()) for _ in range(n)]

# Finding and printing the length of the LIS
result = longestIncreasingSubsequence(arr)
print(result)