LIS | LNDS

/*
Name: Longest increasing/non-decreasing subsequence + reconstruction
Complexity: O(NlogN)
*/

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

const int N=1e5+10;

int n, x, f[N];
vector<int> v, sol;

void add (int x)
{
    int w=lower_bound(v.begin(), v.end(), x)-v.begin(); //lower <==> LIS; upper <==> LNDS

    if (w==0) v.push_back(x);
    else if (w<v.size())
    {
        if (x<v[w])
        {
            v[w]=x;
            f[x]=v[w-1];
        }
    }
    else
    {
        v.push_back(x);
        f[x]=v[w-1];
    }
}

void LIS (int x) //reconstruction
{
    sol.push_back(x);
    if (f[x]) LIS (f[x]);
}

int main()
{
    scanf ("%d", &n);
    for (int i=0; i<n; i++)
    {
        scanf ("%d", &x);
        add (x);
    }

    LIS (v.back());
    printf ("%d\n", v.size());
    for (int i=sol.size()-1; i>=0; i--) printf ("%d ", sol[i]);

    return 0;
}