#include <bits/stdc++.h>
using namespace std;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define IN(x,c) (find(c.begin(),c.end(),x) != (c).end())
#define REP(i,n) for (int i=0;i<(int)(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define INIT(a,v) memset(a,v,sizeof(a))
template<class A, class B> A cvt(B x) { stringstream ss; ss<<x; A y; ss>>y; return y; }

#define SPC << " " <<
#define DEBUG(x) cerr << #x << " = "; cerr << x << endl;
#define DEBUG_ITER(x) cerr << #x << " = "; for (auto _ : x) cerr << _ << ' '; cerr << endl;

typedef long long int64;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef array<int,3> III;

#define N 1000000

int n;
int x[N];

int mem[N];

int lis(int i) {
	if (mem[i]>0) return mem[i];
	int r=1;
	for (int j=i+1; j<n; j++) {
		if (x[j]>x[i]) {
			int rj=1+lis(j);
			r = max(r, rj);
		}
	}
	mem[i]=r;
	return r;
}

int f[N];
int g[N];

int bit[N+1];

int get(int i) {
	int v=0;
	for (int x=i;x>0;x-=x&-x) {
		v=max(v, bit[x]);
	}
	return v;
}

void put(int i, int v) {
	for (int x=i;x<=N;x+=x&-x) {
		bit[x]=max(bit[x], v);
	}
}

int main() {
	freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	//cin >> n;
	n=1000000;
	REP (i,n) {
		//cin >> x[i];
		x[i]=1+rand()%N;
	}
	int r;
	/*
	r=0;
	REP (i,n) {
		int ri = lis(i);
		r = max(r, ri);
	}
	cout << r << endl;

	r = 0;
	for (int i=n-1;i>=0;i--) {
		f[i]=1;
		for (int j=i+1; j<n; j++) {
			if (x[j]>x[i]) {
				f[i] = max(f[i], 1+f[j]);
			}
		}
		r = max(r, f[i]);
	}
	cout << r << endl;

	r = 0;
	for (int i=0;i<n;i++) {
		g[i]=1;
		for (int j=0; j<i; j++) {
			if (x[j]<x[i]) {
				g[i] = max(g[i], 1+g[j]);
			}
		}
		//printf("%d: %d\n",i,g[i]);
		r = max(r, g[i]);
	}
	cout << r << endl;
	*/
	r = 0;
	for (int i=0;i<n;i++) {
		g[i]=1+get(x[i]-1);
		put(x[i], g[i]);
		//printf("%d: %d\n",i,g[i]);
		r = max(r, g[i]);
	}
	cout << r << endl;

	return 0;
}