/** Compute a longest increasing subsequence of the range [begin, end).
 * NOTE THAT THIS FUNCTION DOES _NOT_ SOLVE THE PROBLEM!
 *
 * Fails if <....>
 */
template <typename InputIterator, typename OutputIterator>
OutputIterator lis(InputIterator begin, InputIterator end, OutputIterator out) {
  bool first = true;
  InputIterator last(begin);

  for(InputIterator it = begin; it != end; ++it) {
    if(first || *it > *last) {
      *out++ = *it;
      last = it;
    }
    first = false;
  }

  return out;
}




/*
 * Example of how to use the lis function above:
 */

#include <iostream>
#include <iterator>
#include <vector>

using namespace std;

int main(void) {
  vector<int> sequence;
  int i;

  /* 
   * Read the sequence of elements here...
   */
  while(scanf("%d", &i) == 1) {
    sequence.push_back(i);
  }

  vector<int> answer;
  lis(sequence.begin(), sequence.end(), back_inserter(answer));

  cout << "Length: " << (answer.size()) << endl;
  cout << "Sequence:" << endl;
  for (vector<int>::iterator it = answer.begin(); it != answer.end(); ++it)
    cout << *it << endl;

  return 0;
}