#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define geth(n) (n->h = 1 + max(n->l->h, n->r->h))
#define MAXINT 2000001
struct node;
struct key
{
int best, val, poz;
struct node * pre;
};
struct node
{
struct key k;
int h;
struct node *l, *r;
} *R, *NIL;
typedef struct node node;
int compare(struct key a, struct key b)
{
if (a.val != b.val)
return a.val - b.val;
return a.best - b.best;
}
int is_equal(struct key a, struct key b)
{
return a.best == b.best && a.val == b.val && a.poz == b.poz && a.pre == b.pre;
}
void init(void)
{
R = NIL = (node *) malloc(sizeof(node));
NIL->k.best = NIL->k.poz = 0,
NIL->l = NIL->r = NIL->k.pre = NULL;
NIL->k.val = MAXINT;
NIL->k.best = 1;
}
node* rotleft(node *n)
{
node *t = n->l;
n->l = t->r, t->r = n,
geth(n), geth(t);
return t;
}
node* rotright(node *n)
{
node *t = n->r;
n->r = t->l, t->l = n,
geth(n), geth(t);
return t;
}
node* balance(node *n)
{
geth(n);
if (n->l->h > n->r->h + 1)
{
if (n->l->r->h > n->l->l->h)
n->l = rotright(n->l);
n = rotleft(n);
}
else
if (n->r->h > n->l->h + 1)
{
if (n->r->l->h > n->r->r->h)
n->r = rotleft(n->r);
n = rotright(n);
}
return n;
}
node* insert(node *n, struct key k)
{
if (n == NIL)
{
n = (node *) malloc(sizeof(node));
n->k = k, n->h = 1, n->l = n->r = NIL;
return n;
}
if (compare(k, n->k) < 0)
n->l = insert(n->l, k);
else
n->r = insert(n->r, k);
return balance(n);
}
node* erase(node *n, struct key k)
{
node *t;
if (n == NIL) return n;
if (is_equal(n->k, k))
{
if (n->l == NIL || n->r == NIL)
{
t = n->l == NIL ? n->r : n->l;
free(n); return t;
}
else
{
for (t = n->r; t->l != NIL; t = t->l);
n->k = t->k,
n->r = erase(n->r, t->k);
return balance(n);
}
}
if (compare(k, n->k) < 0)
n->l = erase(n->l, k);
else
n->r = erase(n->r, k);
return balance(n);
}
node* search_best(node *n, int val)
{
node *best;
if (n == NIL) return NIL;
if (n->k.val >= val)
return search_best(n->l, val);
best = search_best(n->r, val);
if (best != NIL) {
if (best->k.val < val)
return best;
}
if (n->k.val < val)
return n;
return NIL;
}
void print_tree(int tab, node *n) {
int i;
if (n == NIL)
return;
if (n->l)
print_tree(tab, n->l);
for (i = 0; i < tab - n->h; i++) printf(" ");
printf("[%4d %4d %4d %4d]\n", n->k.val, n->k.best, n->k.poz, n->k.pre == NULL ? -1 : n->k.pre->k.poz);
if (n->r)
print_tree(tab, n->r);
}
int main()
{
int n, m, i;
int *v, *s;
struct key a, maxglobal;
node *best;
FILE *f = fopen("scmax.in", "r");
FILE *g = fopen("scmax.out", "w");
fscanf(f,"%d\n",&n);
v = (int*)malloc(n*sizeof(int));
for(i=0;i<n;i++)
fscanf(f,"%d ",&v[i]);
init();
maxglobal.best = 1;
a.val = v[0];
a.best = 1;
a.poz = 0;
a.pre = NIL;
R = insert(R, a);
for(i = 1; i < n ; i++){
best = search_best(R, v[i]);
if (best == NIL) {
a.val = v[i];
a.best = 1;
a.poz = i;
a.pre = NIL;
} else {
a.val = v[i];
a.best = 1 + best->k.best;
a.poz = i;
a.pre = best;
}
R = insert(R, a);
// print_tree(R->h, R);
// printf("----\n");
if (a.best > maxglobal.best)
maxglobal = a;
}
m = maxglobal.best;
s = (int*)malloc(m*sizeof(int));
for (i = m-1; i >= 0; i--) {
s[i] = v[maxglobal.poz];
best = maxglobal.pre;
maxglobal = best->k;
}
fprintf(g,"%d\n",m);
for(i=0;i<m;i++)
fprintf(g,"%d ",s[i]);
fprintf(g,"\n");
fclose(f);
fclose(g);
free(v);
free(best);
free(s);
return 0;
}