/*轉載大牛的程序：
   先放著-_-
nlogn的最大上升子序列長度算法
　　傳統的最大上升子序列采用n2的動態規劃算法，就求解一個最大上升子序列的具體序列來說，
暫時找不到更快的算法，但是如果只需要求解這個序列的長度，則存在一個更快的算法，復雜度是nlog2n。

 

　　對于一個序列a[0]...a[n]，設F[i]表示到第i個數為止的最大上升子序列，我們考慮如這種情況，存
在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

　　則此時F[i]應該由F[x]擴展而來，因為可能存在z滿足

(1) y<x<z<i; 

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

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

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

　　求解的過程依然是一個動態規劃的過程，我們采用一個數組d[k]，來描述到狀態i時長度為k的子序列最后一
個元素的最小值。從狀態i-1轉移到狀態i時，a[i]的加入影響到數組中的d[k]，k滿足

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

此時有

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

　　由此我們會發現數組d一個明顯的特征，即d是一個單調上升的序列，利用這個特性，我們可以采用二分法來
查找k的值，這樣使得整體的時間復雜度從原來的n2變為nlog2n，但是在設計過程中應該要注意到數組d的首元素
和尾元素的處理。最后，我們所需要的值就是在末狀態時d數組的最大下標值，這里值得注意的是數組d的下表的
最大值應該是在變化的——反觀定義則可明顯地得到這個特性。

　　一下是一段源代碼，測試過一個小數據，設計中發現整個算法的難點在于二分法查找的設計。
*/

#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;
}