longest_increasing_subsequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll max_ll(ll x, ll y){
    return ((x>y)?(x):(y));
}
int main()
{
    ll n;
    cin>>n;
    ll a[n+1];
    for (ll i=1; i<=n; i++) cin>>a[i];
    ll dp[n+1];
    multiset<pair<ll,ll>> s;
    s.insert({a[1],1});
    dp[1]=1;
    for (ll i=2; i<=n; i++){
        s.insert({a[i],i});
        dp[i]=1;
        for (auto it=s.find({a[i],i}); it!=s.begin(); it--){
            if ((*it).first<a[i]) dp[i]=max_ll(dp[i],dp[(*it).second]+1);
        }
        auto it=s.begin();
        if ((*it).first<a[i]) dp[i]=max_ll(dp[i],dp[(*it).second]+1);
    }
    for (ll i=1; i<=n; i++) dp[n]=max_ll(dp[n],dp[i]);
    cout<<dp[n];
}