#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 6,INF = 1e6 + 4;
int a[N],dp[N];
int main(){
	int n;
	scanf("%d",&n);
	for (int i = 1; i <= n; ++i)
		scanf("%d",&a[i]);
	int len_dp = 1,ios;
	for (int i = 1; i <= n; ++i){
		dp[i] = INF;
		if (a[i] > dp[len_dp]){
			dp[++len_dp] = a[i];
			ios = a[i];
		}
		else{
			int l = 0,r = len_dp,mid;
			while(l <= r){
				mid = (l + r) >> 1;
				if (dp[mid] > a[i]) r = mid - 1;
				else l = mid + 1;
			}
			dp[l] = a[i];
		}
	}
	printf("%d",len_dp);
	return 0;
}