#include <algorithm>
using namespace std;

#define DIM 100005
#define MAX 10005

char s[ MAX ];
int N, XXX, A[ DIM ];
int ind, poz, id_xxx, cnt_s, ind_aux, lim_sup, arb[ 3*DIM ], ant[ DIM ], sol[ DIM ], id_1[ DIM ], id_2[ DIM ];

struct cmp {

    bool operator()( const int &x, const int &y ) {

        return A[ x ] < A[ y ];
    }
};

inline void query( const int &nod, const int &st, const int &dr ) {

    int mij;

    if( dr <= lim_sup ) {

        if( sol[ arb[ nod ] ] > sol[ ind_aux ] )
            ind_aux = arb[ nod ];

        return;
    }

    mij = (st+dr) / 2;
    query( nod<<1, st, mij );
    if( mij < lim_sup )
        query( (nod<<1) + 1, mij+1, dr );
}

inline void update( const int &nod, const int &st, const int &dr ) {

    int mij;

    if( st == dr ) {

        if( sol[ ind ] > sol[ arb[ nod ] ] )
            arb[ nod ] = ind;

        return;
    }

    mij = (st+dr) / 2;
    if( poz <= mij )
        update( nod<<1, st, mij );
    else
        update( (nod<<1) + 1, mij+1, dr );

    if( sol[ arb[ nod<<1 ] ] > sol[ arb[ (nod<<1) + 1 ] ] )
        arb[ nod ] = arb[ nod<<1 ];
    else
        arb[ nod ] = arb[ (nod<<1) + 1 ];
}

void print( const int &ind ) {

    if( ant[ ind ] )
        print( ant[ ind ] );

    printf( "%d ", A[ ind ] );
}

inline void read( int &val ) {

    while( !isdigit( s[ cnt_s ] ) )
        if( ++cnt_s == MAX ) {

            fread( s, 1, MAX, stdin );
            cnt_s = 0;
        }

    val = 0;
    while( isdigit( s[ cnt_s ] ) ) {

        val = val*10 + s[ cnt_s ] - '0';
        if( ++cnt_s == MAX ) {

            fread( s, 1, MAX, stdin );
            cnt_s = 0;
        }
    }
}

int main() {

    freopen( "scmax.in", "r", stdin );
    freopen( "scmax.out", "w", stdout );

    int i, cnt_1, cnt_2;

    cnt_s = MAX-1;

    read( N );
    for( i = 1; i <= N; ++i ) {

        read( A[ i ] );
        id_1[ i ] = i;
    }

    sort( id_1 + 1, id_1 + N+1, cmp() );

//    for( int i = 1; i <= N; ++i )
//        printf( "%d\n", id_1[ i ] );

    cnt_1 = cnt_2 = 0;
    for( i = 1; i <= N; ++i ) {

        if( A[ id_1[ i ] ] != A[ id_1[ i-1 ] ] ) {

            cnt_1 += cnt_2 + 1;
            cnt_2 = 0;
        }
        else
            ++cnt_2;

        id_2[ id_1[ i ] ] = cnt_1;
    }

//    for( int i = 1; i <= N; ++i )
//        printf( "%d\n", id_2[ i ] );

    for( i = 1; i <= N; ++i ) {

        ind_aux = 0;
        if( id_2[ i ] > 1 ) {

            lim_sup = id_2[ i ] - 1;
            query( 1, 1, N );
        }

        sol[ i ] = sol[ ind_aux ] + 1;
        ant[ i ] = ind_aux;

        ind = i;
        poz = id_2[ i ];
        update( 1, 1, N );

        if( sol[ i ] > XXX ) {

            XXX = sol[ i ];
            id_xxx = i;
        }
    }

    printf( "%d\n", XXX );
//    print( id_xxx );

    return 0;
}