14003.cpp

#include <iostream>
#include <vector>

#define MAX 1000010

using namespace std;

int N;
int input[MAX], idx[MAX], LIS[MAX], ans[MAX];
int len;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	cin >> input[0];
	LIS[len++] = input[0];
	idx[0] = 0;

	for (int i = 1; i < N; i++) {
		cin >> input[i];

		if (input[i] > LIS[len - 1]) {
			LIS[len++] = input[i];
			idx[i] = len - 1;
		}
		else {
			int *iter = lower_bound(LIS, LIS + len, input[i]);
			*iter = input[i];
			idx[i] = (iter - LIS);
		}
	}

	int size = len;
	cout << size << '\n';
	
	len = 0;
	int cur = size - 1;
	for (int i = N - 1; i >= 0; i--) {
		if (cur == idx[i]) {
			ans[len++] = input[i];
			cur--;
		}
	}

	for (int i = len - 1; i >= 0; i--) {
		cout << ans[i] << ' ';
	}

	cout << '\n';

	return 0;
}