O(nlogn) LIS

ll M, N, K;
vector<ll> lis;
vector<ll> v;
ll ans = 0;

cin >> N;

for (int i = 0; i < N; i++)
{
	cin >> K;
	v.push_back(K);
}

lis.push_back(-INF);

for (int i = 0; i < N; i++)
{
	if (lis.back() < v[i])
	{
		lis.push_back(v[i]);
		ans++;
	}
	else
	{
		auto it = lower_bound(lis.begin(), lis.end(), v[i]);
		*it = v[i];
	}
}