/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu
************************************************/

import java.io.*;
import java.nio.*;
import java.util.*;

public class P02Ascending {

  private static final String FileInputName = "aufsteigend.in";
  private static final String FileOutputName = "aufsteigend.out";

  private List<Integer> a;
  private IntBuffer v, vPred;

  private int imax;

  P02Ascending(List<Integer> list) {
    this.a = list;
    this.v = IntBuffer.allocate(list.size());
    this.vPred = IntBuffer.allocate(list.size());
  }

  void process() {
    int j, i, n;
    v.put(1);
    vPred.put(-1);

    this.imax = 0;
    n = (int) a.size();
    for (i = 1; i < n; i++) {
      v.put(1);
      vPred.put(-1);
      for (j = 0; j < i; j++)
        if (a.get(j) < a.get(i) && v.get(j) + 1 > v.get(i)) {
          // replace the last element of the buffer(at the "position()-1")
          v.put(v.position() - 1, v.get(j) + 1);
          vPred.put(vPred.position() - 1, j);
        }
      if (v.get(i) > v.get(imax))
        this.imax = i;
    }
  }

  private void recoverSubstring(int i, PrintStream out) {
    if (vPred.get(i) + 1 != 0)
      recoverSubstring(vPred.get(i), out);
    out.print(a.get(i));
    out.print(' ');
  }

  void writeData(PrintStream out) {
    out.println("--- Eingabe: ");
    out.print("Laenge: ");
    out.println(a.size());
    out.print("Die Elemente: ");
    for (Integer i : a) {
      out.print(i);
      out.print(' ');
    }
    out.println();
    out.println("--- Ausgabe: ");
    out.print(" Laengste aufsteigende Teilfolge: ");
    recoverSubstring(imax, out);
    out.println();
    out.print(" Laenge: ");
    out.println(v.get(this.imax));
  }

  public static void main(String[] args) throws IOException {
    Scanner scanner = null;
    PrintStream out = null;
    try {
      out = new PrintStream(new File(FileOutputName));
      scanner = new Scanner(new File(FileInputName));
      List<Integer> list = new ArrayList<Integer>();
      while (scanner.hasNextInt()) {
        list.add(scanner.nextInt());
      }
      P02Ascending p = new P02Ascending(list);
      p.process();
      p.writeData(out);
    } finally {
      if (scanner != null) {
        scanner.close();
      }
      if (out != null) {
        out.close();
      }
    }
  }
}