program MaxRostVybrPosl;
  { program hleda delku nejdelsi rostouci vybrane
    posloupnosti ze vstupni posloupnosti  }
  { slozitost N*log(N)  }

const MAX = 20;

type

  vektor = array [1..MAX] of integer;
  delka  = 0..MAX;
  tab    = record
             A   : vektor;  { posloupnost }
             DEL : delka;   { delka skutecne vyuzite casti posloupnosti A }
           end;

var

  VSTUP : text;   { vstupni soubor obsahuje
                    na kazde radce jedno cislo vstupujici posloupnosti }

  VYSTUP : text;  { vystupni soubor, do ktereho take zkopirujeme vstupni
                    posloupnost  }

  Z ,            { tabulka se vstupni posloupnosti }

  MIN   : tab;   { tabulka obsahuje rostouci posloupnost cisel
                   MIN.A[I] - minimalni posledni prvek rostouci
                              vybrane posloupnosti delky I
                              z dosud proverene casti posloupnosti Z.A }
 {pomocne promenne}
  I,J : integer;
  S   : string;

  procedure sniz(var T:tab; X:integer);
    { predpoklada, ze X<=T.A[A.DEL] ,
      najde nejmensi index J takovy, ze X<=A[J]
      a "snizi" hodnotu A[J] na hodnotu X }
  var
    J,
    D,H : delka;  { podezrele indexy jsou D..H }
  begin
    with T do
      begin
        D:=1; H:=DEL;
        while H>D do   { dokud je vice podezrelych }
          begin
            J:=(H+D) div 2;
            if X > A[J] then D:=J+1
                        else H:=J;
          end;
        A[D]:=X;
      end;
  end;

begin

  writeln('Zadej jmeno vstupniho souboru');
  readln(S);
  assign(VSTUP,S);
  reset(VSTUP);

  writeln('Zadej jmeno vystupniho souboru');
  readln(S);
  assign(VYSTUP,S);
  rewrite(VYSTUP);

    { -- hlavicka vystupu do souboru VYSTUP,
         do nej zkopirujeme i vstupni posloupnost -- }

  writeln(VYSTUP,'Nejdelsi vybrana posloupnost z posloupnosti:');


    { -- vstup posloupnosti ze souboru VSTUP do tabuly Z -- }

  with Z do
    begin
      DEL:=0;
      while not eof(VSTUP) do
        begin
          DEL:= DEL+1;
          readln(VSTUP,A[DEL]);
          writeln(VYSTUP,A[DEL]);
        end;
    end;

  { -- zaplneni pomocne tabulky MIN -- }

  with MIN do
    begin

      {inicializace }

      DEL  := 1;       { delka nejdelsi rostouci posloupnosti }
      A[1] := Z.A[1];

      for I:=2 to Z.DEL do  { posloupne zpracovavame
                              dalsi cleny posloupnosti Z.A}
        begin

          if Z.A[I]>A[DEL] then { prodlouzim tabulku MIN }
            begin
              DEL:= DEL+1;
              A[DEL]:=Z.A[I];
            end
                           else { snizi vhodny index v tabulce MIN }
            sniz(MIN,Z.A[I]);

        end;

      writeln(VYSTUP,' ma delku ', DEL);

     { ladící tisk pole MIN.A
	    for I:=1 to DEL do
        writeln(vystup,A[I]); }

    end;

    close (Vystup);


end.