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