LIS using Segment Tree

// I can't tell you what it really is,
// I can only tell you what it feels like.
#include "bits/stdc++.h"

using namespace std;

#define int long long
#define F first
#define S second
#define rep(i,a,n)  for (int i = a; i <= n; ++i)
#define fo(i, n)   for (int i = 1; i <= n; ++i)
#define all(v)  v.begin(), v.end()
#define pb push_back
#define P pair < int, int >
#define fast      ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define reno(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}

template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a << ' ';
	err(++it, args...);
}

const int N = 1e6 + 5;
int tree[N<<2];
pair < int, int > p[N];
void upd(int l, int r, int pos, int val, int x) {
	if(r < pos || pos < l)
		return;
	if(l == r and pos == r){
		// cout << l << ' ' << val << '\n';
		tree[x] = val;
		return;
	}
	int mid = l + r >> 1;
	upd(l, mid, pos, val, x << 1);
	upd(mid + 1, r, pos, val, x << 1 | 1);
	tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
int query(int l, int r, int ql, int qr, int x) {
	if(qr < l || r < ql || qr < ql)
		return 0;
	if(ql <= l and r <= qr)
		return tree[x];
	int mid = l + r >> 1;
	int a = query(l, mid, ql, qr, x << 1);
	int b = query(mid + 1, r, ql, qr, x << 1 | 1);
	return max(a, b);
}
signed main(){
    fast;
    int n, temp;
    cin >> n;

    fo(i, n) {
    	cin >> temp;
    	p[i].F = temp;
    	p[i].S = i;
    }

    sort(p + 1, p + 1 + n, []
    	(P x, P y) {
			// For Strictly Increasing
    		if(x.F == y.F)
    			return x.S > y.S;
    		return x.F < y.F;
    	}
    );

    fo(i, n) {
    	// cout << p[i].F << ' ' << p[i].S << ' ';
    	int let = query(1, n, 1, p[i].S - 1, 1);
    	//cout << let << '\n';
    	upd(1, n, p[i].S, let + 1, 1);

    }
    cout << tree[1];


















	return 0;
}