#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>

#define io_r freopen("input.txt","r",stdin);
#define io_w freopen("output.txt","w",stdout);
#define io_file io_r; io_w;

#define ll long long
#define PB push_back
#define MP make_pair
#define f(i,a,b) for (int i = a; i<b; i++)
#define rep(i,n) for (int i = 0; i<n; i++)
#define clr(x, y) memset(x, y, sizeof x)

#define MAX 1000100
#define INF INT_MAX/2

using namespace std;

int v[MAX];
int pd[MAX], tailTable[MAX];

int CeilIndex(int A[], int l, int r, int key) {
    int m;
 
    while( r - l > 1 ) {
        m = l + (r - l)/2;
        (A[m] >= key ? r : l) = m; // ternary expression returns an l-value
    }
 
    return r;
}
 
int lis(int A[], int size) {
    int len;
 
    tailTable[0] = A[0];
    len = 1;
    for( int i = 1; i < size; i++ ) {
        if( A[i] < tailTable[0] )
            tailTable[0] = A[i];
        else if( A[i] > tailTable[len-1] )
            tailTable[len++] = A[i];
        else
            tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i];
    }
 
    return len;
}

int main (){
	int n;
	scanf ("%d", &n);
	
	rep (i, n)  scanf ("%d", &v[i]);

	printf ("%d\n", lis(v, n));
	
	return 0;
}

import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;



public class Solution {
    FastScanner input;
    PrintWriter output;
    final int MAX_N = (int)(1e6+6);
    final int MAX_A = (int)(1e5+5);


    public static void main(String[] arg) {
        new Solution().run();
    }

    void run() {
        try {
            boolean debug = false;
            //boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
            if (debug) input = new FastScanner(new File("longest_increasing_subsequent.in"));
            else input = new FastScanner();
            output = new PrintWriter(System.out);
            solve();
            output.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }


    void solve() throws IOException {
    	int n = input.nextInt(), res = 0;
    	int f[] = new int[MAX_N];
    	Arrays.fill(f, -1);
    	for (int i = 0; i < n; ++i) {
    		int a = input.nextInt();
    		if (a > f[res]) f[++res] = a;
    		else if (a < f[1]) f[1] = a;
    		else {
    			int l = 1, r = res-1, t = -1;
    			while (l <= r) {
    				int mid = (l+r)>>1;
    				if (f[mid] < a) t = l = mid+1;
    				else r = mid-1;
    			}
    			if (t > 0) f[t] = a;
    		}
    	}
    	output.println(res);
    }
}



class FastScanner {
    BufferedReader br;
    StringTokenizer st;
    FastScanner(File f) {
        try {
            br = new BufferedReader(new FileReader(f));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
    FastScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null) return null;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
    int nextInt()       {   return Integer.parseInt(next());    }
    long nextLong()     {   return Long.parseLong(next());      }
    double nextDouble() {   return Double.parseDouble(next());  }
}



class Pair<T1 extends Comparable<T1>, T2 extends Comparable<T2>> implements Comparable<Pair<T1, T2>> {
    public T1 first;
    public T2 second;
    public Pair(T1 first, T2 second) {
        this.first = first;
        this.second = second;
    }
    public int compareTo(Pair<T1, T2> o) {
        if (first.compareTo(o.first) != 0) return first.compareTo(o.first);
        return second.compareTo(o.second);
    }
}
 

def subsequence(seq):
    if not seq:
        return seq

    M = [None] * len(seq)    # offset by 1 (j -> j-1)
    P = [None] * len(seq)

    # Since we have at least one element in our list, we can start by 
    # knowing that the there's at least an increasing subsequence of length one:
    # the first element.
    L = 1
    M[0] = 0

    # Looping over the sequence starting from the second element
    for i in range(1, len(seq)):
        # Binary search: we want the largest j <= L
        #  such that seq[M[j]] < seq[i] (default j = 0),
        #  hence we want the lower bound at the end of the search process.
        lower = 0
        upper = L

        # Since the binary search will not look at the upper bound value,
        # we'll have to check that manually
        if seq[M[upper-1]] < seq[i]:
            j = upper

        else:
            # actual binary search loop
            while upper - lower > 1:
                mid = (upper + lower) // 2
                if seq[M[mid-1]] < seq[i]:
                    lower = mid
                else:
                    upper = mid

            j = lower    # this will also set the default value to 0

        P[i] = M[j-1]

        if j == L or seq[i] < seq[M[j]]:
            M[j] = i
            L = max(L, j+1)

    # Building the result: [seq[M[L-1]], seq[P[M[L-1]]], seq[P[P[M[L-1]]]], ...]
    result = []
    pos = M[L-1]
    for _ in range(L):
        result.append(seq[pos])
        pos = P[pos]

    return result[::-1]    # reversing
i=0
import sys
seq = []
i=0
for line in sys.stdin:
    if i == 0:
        i+=1
    else:
        seq.append(int(line.split()[0]))

print (len(subsequence(seq)))

# Enter your code here. Read input from STDIN. Print output to STDOUT
from bisect import bisect_left
def LongestIncreasingSubsequence(S):
    
    head = []
    tail = [None]

    for x in S:
        i = bisect_left(head,x)
        if i >= len(head):
            head.append(x)
            if i > 0:
                tail.append((head[i-1],tail[i-1]))
        elif head[i] > x:
            head[i] = x
            if i > 0:
                tail[i] = head[i-1],tail[i-1]

    if not head:
        return []

    output = [head[-1]]
    pair = tail[-1]
    while pair:
        x,pair = pair
        output.append(x)

    output.reverse()
    return len(output)
n = int(raw_input())
a = list()
for i in range(n):
    temp = int(raw_input())
    a.append(temp)
print LongestIncreasingSubsequence(a)

#include <stdio.h>

int n,a[1000000],b[1000000]; 

int getRight(int *Arr,int left,int right,int value)
{
    int mid;
    while(right>left+1)
    {
        mid=left+(right-left)/2;
        if(Arr[mid]>=value)right=mid;
        else left=mid;
    }
    return right;
}
 
int CalcLIS()
{
    int i,res=1;
    b[0]=a[0];
    for(i=1;i<n;i++)
    {
        if(a[i]<b[0])
            b[0]=a[i];
        else if(a[i]>b[res-1])
            b[res++]=a[i];
        else
            b[getRight(b,-1,res-1,a[i])]=a[i];
    }
    return res;
}
 
int main()
{
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    printf("%d",CalcLIS());
    return 0;
}