1. C, Andreas Kunft


/*
 * ACM Programming Contest
 * Problem: 481 (What Goes Up)
 * Status: Accepted
 * Language: ANSI C
 * Runtime: 0.128
 * Date: 2009-05-26 22:04:53
 * Author: Andreas Kunft
 */

#include <stdio.h>

int a[100000000];
int p[100000000], b[100000000];
int count = 0;

int bIndex = 0;

void subSequence() {
int u, v, i;

b[bIndex] = 0;

for (i = 1; i < count; i++) {
if (a[b[bIndex]] < a[i]) {
p[i] = b[bIndex];
b[++bIndex] = i;
continue;
}

for (u = 0, v = bIndex; u < v;) {
int c = (u + v) / 2;
if (a[b[c]] < a[i]) {
u = c + 1;
} else {
v = c;
}
}

if (a[i] < a[b[u]]) {
if (u > 0) {
p[i] = b[u - 1];
}
b[u] = i;
}
}

for (u = bIndex + 1, v = b[bIndex]; u--; v = p[v]) {
b[u] = v;
}

}

void recover(int i) {
if (p[i] + 1)
recover(p[i]);
printf("%d\n", a[i]);
}

int main() {
int in = 0;
while (scanf("%d", &in) == 1) {
a[count++] = in;
}
subSequence();
printf("%d\n-\n", bIndex + 1);
int i;
for (i = 0; i < bIndex + 1; i++)
printf("%d\n", a[b[i]]);
return 0;
}