LIS O(nlogn)

#include <bits/stdc++.h>
using namespace std;

#define ll long long

ll n;
ll arr[100005], L[100005];
ll I[100005]; // last elements of sequence of i-th length

const ll inf = 10000000000;

int main()
{
    cin >> n;
    for (int i = 0; i<n; i++)
        cin >> arr[i];

    I[0] = -inf;
    for (int i = 1; i<=n; i++)
        I[i] = inf;

    ll maxLength = 0, pos = -1;

    for (int i = 0; i<n; i++)
    {
        ll l = 0, r = maxLength;
        while (l <= r)
        {
            ll mid = (l+r)/2;
            if (I[mid] < arr[i])
                l = mid+1;
            else r = mid-1;
        }

        I[l] = arr[i];
        L[i] = l;
        if (l > maxLength)
        {
            maxLength = l;
            pos = i;
        }
    }

    cout << maxLength << endl;
    deque <ll> ans;   // reconstructing results
    ans.push_front(arr[pos]);

    for (int j = pos-1; j>=0; j--)
    {
        if (arr[j] < arr[pos] and L[j] == L[pos]-1)
        {
            ans.push_front(arr[j]);
            pos = j;
        }
    }

    for (int i = 0; i<ans.size(); i++)
        cout << ans[i] << " ";
}