/*轉(zhuǎn)載大牛的程序：
   先放著-_-
nlogn的最大上升子序列長(zhǎng)度算法
　　傳統(tǒng)的最大上升子序列采用n2的動(dòng)態(tài)規(guī)劃算法，就求解一個(gè)最大上升子序列的具體序列來(lái)說(shuō)，
暫時(shí)找不到更快的算法，但是如果只需要求解這個(gè)序列的長(zhǎng)度，則存在一個(gè)更快的算法，復(fù)雜度是nlog2n。

 

　　對(duì)于一個(gè)序列a[0]...a[n]，設(shè)F[i]表示到第i個(gè)數(shù)為止的最大上升子序列，我們考慮如這種情況，存
在0<=y<x<i=n，若滿足

(1) y<x<i;

(2) a[x]<a[y]<a[i]; 

(3) |F[x]| == |F[y]|;

 (4) a[j] < a[x], y < j < x

　　則此時(shí)F[i]應(yīng)該由F[x]擴(kuò)展而來(lái)，因?yàn)榭赡艽嬖趜滿足

(1) y<x<z<i; 

(2) a[x]<a[z]<a[y]<a[i]

(3) z < min{j | a[j]>a[y], j > x}

　　則此時(shí)用F[x]擴(kuò)展得到F[i]將長(zhǎng)于F[y]擴(kuò)展得到的子序列。 由此可得出結(jié)論，原序列第i個(gè)元素之前最長(zhǎng)
子序列的解可能存在很多，但我們只需要盡可能使得那個(gè)最長(zhǎng)子序列的最后一個(gè)元素的值最小，就能向后擴(kuò)展得
到原串最長(zhǎng)子序列。

　　求解的過(guò)程依然是一個(gè)動(dòng)態(tài)規(guī)劃的過(guò)程，我們采用一個(gè)數(shù)組d[k]，來(lái)描述到狀態(tài)i時(shí)長(zhǎng)度為k的子序列最后一
個(gè)元素的最小值。從狀態(tài)i-1轉(zhuǎn)移到狀態(tài)i時(shí)，a[i]的加入影響到數(shù)組中的d[k]，k滿足

k = max{a[i]>d[j]} + 1

此時(shí)有

d[k] = min{d[k], a[i]}

　　由此我們會(huì)發(fā)現(xiàn)數(shù)組d一個(gè)明顯的特征，即d是一個(gè)單調(diào)上升的序列，利用這個(gè)特性，我們可以采用二分法來(lái)
查找k的值，這樣使得整體的時(shí)間復(fù)雜度從原來(lái)的n2變?yōu)閚log2n，但是在設(shè)計(jì)過(guò)程中應(yīng)該要注意到數(shù)組d的首元素
和尾元素的處理。最后，我們所需要的值就是在末狀態(tài)時(shí)d數(shù)組的最大下標(biāo)值，這里值得注意的是數(shù)組d的下表的
最大值應(yīng)該是在變化的——反觀定義則可明顯地得到這個(gè)特性。

　　一下是一段源代碼，測(cè)試過(guò)一個(gè)小數(shù)據(jù)，設(shè)計(jì)中發(fā)現(xiàn)整個(gè)算法的難點(diǎn)在于二分法查找的設(shè)計(jì)。
*/

#include <cstdio>
#include <cstdlib>
#include <climits>
#include <iostream>
using namespace std;
#define MAX 1000
int a[MAX];
int d[MAX];
int max_subsequence (const int size )
{
    int n;
    d[ n = 0 ] = a[ 0 ];
    for ( int i = 1; i < size; i++ )
        if ( d[ n ] < a[ i ] )
            d[ ++n ] = a[ i ];
        else if ( d[ 0 ] > a[ i ] )
            d[ 0 ] = a[ i ];
        else
        {
            int left = 0, right = n, mid = n / 2, key = a[ i ];
            while ( left < right ){
                if ( d[ mid ] == key )
                {
                    mid--;
                    break;
                }
                if ( d[ mid ] > key )
                {
                    right = mid;
                    mid = ( left + right ) / 2;
                }
                else if ( mid > left )
                {
                    left = mid;
                    mid = ( left + right ) / 2;
                }
                else
                    break;
            }
            if ( d[ mid + 1 ] > key )
                d[ mid + 1 ] = key;
        
        }
    return n + 1;
}

int main ( )
{
    int n;
    scanf ( "%d", &n );
    for ( int i = 0; i < n; i++ )
        scanf ( "%d", &a[ i ] );
    printf ( "%d\n", max_subsequence ( n ) );
  //  system ( "pause" );
 return 0;
}