lis.cpp

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector<int> vec(n);
	for (int& i : vec) cin>>i;
	constexpr int INF = 1e8;
	const int len = vec.size();
	vector<int> dp(len,INF);
	for (int i = 0; i < len; i++) 
		*lower_bound(dp.begin(),dp.end(),vec[i]) = vec[i];
	cout << distance(dp.begin(),lower_bound(dp.begin(),dp.end(),INF)) << endl;

	return 0;
}