1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 481 - What goes up
* Link: http://uva.onlinejudge.org/external/4/481.html
*
* @author Bastian Hoecker
* @author Philipp Hauck Thalheim
* @version 1.0, 06/21/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.056
*/
#include <vector>
#include <iostream>
using namespace std;

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b) {
vector<int> p(a.size());
int u, v;

if (a.empty())
return;

b.push_back(0);

for (int i = 1; i < a.size(); i++) {
// If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
if (a[b.back()] < a[i]) {
p[i] = b.back();
b.push_back(i);
continue;
}

// Binary search to find the smallest element referenced by b which is just bigger than a[i]
// Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.
for (u = 0, v = b.size() - 1; u < v;) {
int c = (u + v) / 2;
if (a[b[c]] < a[i])
u = c + 1;
else
v = c;
}

// Update b if new value is smaller then previously referenced value
if (a[i] < a[b[u]]) {
if (u > 0)
p[i] = b[u - 1];
b[u] = i;
}
}

for (u = b.size(), v = b.back(); u--; v = p[v])
b[u] = v;
}

/* Example of usage: */
#include <cstdio>
int main() {


int i =0;
int a[100000];
while (scanf("%d",&a[i++]) != EOF);

vector<int> seq(a, a + sizeof(a) / sizeof(a[0]));
vector<int> lis;
find_lis(seq, lis);


cout << lis.size() << endl << "-" << endl;
for (int i = 0; i < lis.size(); i++)
cout << seq[lis[i]] << endl;

return 0;
}