#include <fstream>
#include <algorithm>

#define MAX_N 100000

using namespace std;

struct DP {
    int len, st, dr;

    bool operator < (const DP &a) const {
        if ( len == a.len )
            return st < a.st;
        return len < a.len;
    }
};

struct AIB {
    DP aib[MAX_N + 1];

    void init() {
        int i;

        for ( i = 0; i <= MAX_N; i++ )
            aib[i] = { 0, 0, 0 };
    }
    DP query( int i ) {
        DP maxx;

        maxx = { 0, 0, 0 };
        while ( i > 0 ) {
            maxx = max( maxx, aib[i] );
            i -= (i & -i);
        }

        return maxx;
    }

    void update( int i, DP x ) {
        while ( i <= MAX_N ) {
            aib[i] = max( aib[i], x );
            i += (i & -i);
        }
    }
};


int v[MAX_N], p[MAX_N];
AIB dp;

bool cmp( int a, int b ) {
    return v[a] < v[b];
}

int main() {
    int t, n, val, i, j;
    DP crt;

    ifstream cin( "scmax.in" );
    ofstream cout( "scmax.out" );

    cin >> n;
    for ( i = 0; i < n; i++ ) {
        cin >> v[i];
        p[i] = i;
    }

    sort( p, p + n, cmp );

    i = 0;
    val = 1;
    while ( i < n ) {
        j = i;
        while ( j < n && v[p[i]] == v[p[j]] ) {
            v[p[j]] = val;
            j++;
        }
        i = j;
        val++;
    }

    dp.init();
    int maxLen = 0;
    int minInt = n;
    for ( i = 0; i < n; i++ ) {
        crt = dp.query( v[i] - 1 );
        if ( crt.len > 0 ) {
            crt.len++;
            crt.dr = i;
        } else
            crt = { 1, i, i };

        dp.update( v[i], crt );

        if ( crt.len > maxLen ) {
            maxLen = crt.len;
            minInt = crt.dr - crt.st + 1;
        } else if ( crt.len == maxLen ) {
            if ( crt.dr - crt.st + 1 < minInt )
                minInt = crt.dr - crt.st + 1;
        }
    }

    cout << maxLen << "\n";

    return 0;
}