LIS

/*
Longest Non-Decreasing Subsequence
Vremenska slozenost: O(N*logN)
Memorija: O(N)
*/

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

const int N=1e5+10;

struct Node
{
    int parent;
    Node()
    {
        parent=-1;
    }
} g[N]; //graf (stablo) koji sluzi za rekonstrukciju LISa

int n, a[N], dp[N], lis; // dp[i] <==> idx najmanjeg broja kom je LIS duzine i
vector<int> sol; //rekonstruisan LIS

int bs (int x, int bound) //hocu broj X da stavim na postojeci LIS duzine RET
{
    int l=1, r=bound, mid, ret=0;
    while (l<=r)
    {
        mid=l+(r-l)/2;
        if (dp[mid]==-1 || a[dp[mid]]>x) r=mid-1;
        else
        {
            ret=mid;
            l=mid+1;
        }
    }
    return ret+1; //novi LIS ce biti duzine RET+1
}

void dfs (int v)
{
    sol.push_back(v);
    if (g[v].parent==-1) return;
    dfs (g[v].parent);
}

void reconstruct ()
{
    dfs (dp[lis]);
    reverse (sol.begin(), sol.end()); //tehnicki suvisno
}

int main()
{
    scanf ("%d", &n);
    memset (dp, -1, sizeof dp);

    for (int i=1;i<=n;i++)
    {
        scanf ("%d", &a[i]);

        int idx=bs(a[i], i-1);
        lis=max(lis, idx);

        if (dp[idx]==-1 || a[dp[idx]]>a[i])
        {
            dp[idx]=i;
            if (idx>1) g[i].parent=dp[idx-1]; //koja pozicija je u LISu pre i
        }
    }

    reconstruct();

    printf ("%d\n", lis);
    for (int i=0;i<lis;i++) printf ("%d ", a[sol[i]]);

    return 0;
}