Untitled

#include <bits/stdc++.h>

using namespace std;

#define Chris "test"
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORD(i, a, b) for(int i = (a); i <= (b); ++i)
#define REP(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define All(v) (v).begin(), (v).end()
#define rAll(v) (v).rbegin(), (v).rend()
#define MARK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define el "\n"
#define Chris_ signed main()
#define faster ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define file(Chris) if(fopen(Chris".inp", "r")){freopen(Chris".inp", "r", stdin);freopen(Chris".out", "w", stdout);}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vii;
typedef set<int> sii;
typedef map<int, int> mii;
typedef stack<int> sti;
typedef deque<int> dqi;
typedef queue<int> quei;
typedef unordered_map<int, int> umii;

const int mod = (int) 1e5;
const int INF = (int) 1e9;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n;

void solve(int n)
{
    vii a(n);
    FOR(i, 0, n) cin >> a[i];
    vii l(n, 1);
    FOR(i, 0, n)
    {
        FOR(j, 0, i)
        {
            if(a[i] > a[j])
            {
                l[i] = max(l[i], l[j] + 1);
            }
        }
    }
    cout <<*max_element(All(l)) << el;
}

void solve1(int n)
{
    vii a(n), kq;
    FOR(i, 0, n)
    {
        auto it = lower_bound(All(kq), a[i]);
        if(it == kq.end()) kq.pb(a[i]);
        else *it = a[i];
    }
    cout << kq.size() << el;
}

vii getlis(vii &a)
{
    int n = a.size();
    vii dp(n, 1), seq(n);
    FOR(i, 0, n)
    {
        seq[i] = i;
        FOR(pre, 0, i)
        {
            if(a[pre] < a[i] && dp[pre] + 1 > dp[i])
            {
                dp[i] = 1 + dp[pre];
                seq[i] = pre;
            }
        }
    }
    int ans = -1, tmp = -1;
    FOR(i, 0, n)
    {
        if(dp[i] > ans)
        {
            ans = dp[i];
            tmp = i;
        }
    }
    vii res;
    res.pb(a[tmp]);
    while(seq[tmp] != tmp)
    {
        tmp = seq[tmp];
        res.pb(a[tmp]);
    }
    reverse(All(res));
    return res;
}

vii printLIS(const vii &a)
{
    int n = a.size();
    vii tail, indi(n), pre(n, -1);
    FOR(i, 0, n)
    {
        auto it = lower_bound(All(tail), a[i]);
        int pos = it - tail.begin();
        if(pos == tail.size())
        {
            tail.pb(a[i]);
        }
        else
        {
            tail[pos] = a[i];
        }
        indi[pos] = i;
        if(pos > 0)
        {
            pre[i] = indi[pos - 1];
        }
    }
    vii lis;
    for(int i = indi[tail.size() - 1]; i >= 0; i = pre[i])
    {
        lis.pb(a[i]);
    }
    reverse(All(lis));
    return lis;
}

Chris_
{
    faster
    file(Chris)

    cin >> n;
    vii a(n), kq;
    FOR(i, 0, n) cin >> a[i];
    vii kq1 = printLIS(a);
    cout << kq1.size() << el;
    for(int i : kq1)
    {
        cout << i << " ";
    }
    return 0;
}