sequence_decomposing_fenwick

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<set>

#define long long long
#define nln '\n'

using namespace std;

vector<long> dp;

void update(long ind, long val)
{
	while (ind < (long)dp.size())
	{
		dp[ind] = max(dp[ind], val);
		ind += ind&-ind;
	}
}

long get(long ind)
{
	long mav = 0;
	while (ind > 0)
	{
		mav = max(mav, dp[ind]);
		ind -= ind&-ind;
	}
	return mav;
}

int main()
{
	// Input
	//freopen("lis.inp", "r", stdin);
	long n;
	cin >> n;
	vector<long> a(n+1, 0);
	for (long i = 1; i <= n; ++i)
		cin >> a[i];
	reverse(a.begin()+1, a.end());
	// Compress number
	set<long> num(a.begin()+1, a.end());
	vector<long> tea(num.begin(), num.end());
	reverse(tea.begin(), tea.end());
	tea.push_back(0);
	reverse(tea.begin(), tea.end());

	for (long i = 1; i <= n; ++i)
		a[i] = lower_bound(tea.begin()+1, tea.end(), a[i]) - tea.begin();

	// process by Fenwick
	long ans = 0;
	dp.resize(n+1, 0);
	for (long i = 1; i <= n; ++i)
	{
		long res = get(a[i]);
		update(a[i], res+1);
		ans = max(ans, res+1);
	}
	cout << ans << nln;
	return 0;
}