const
  std_in  = '';
  std_out = '';
  nLine = #10#13;

type
  pttype = ^ttype;

  PArrType = ^arrType;
  arrType =
    array[1 .. 2 * maxint div sizeof(ttype)] of ttype;

  tarray = object
  private
    arr: PArrType;
    SizeOfArray: word;

    { Iterators }
    function first: word;
    function last: word;
    { Iterators }

    procedure swap(i, j: word);
    procedure sort(n, t: word);

    function Allocate(sz: word): PArrType;
    procedure DeAllocate(sz: word);

    procedure SetSize(sz: word);
    function ValidIndex(i: word): boolean;

  public
    constructor init(sz: word);
    destructor done;

    procedure Resize(sz: word);
    function GetSize: word;

    function Input(n: integer;
             s: string): integer;
    function Print(s: string): integer;


    procedure qSort(Left, Right: integer);
    procedure hSort;

    function max: pttype;
    function min: pttype;
    function maxIndex: word;
    function minIndex: word;
    function IndexOf(T: ttype): word;
    procedure Invert;

    function Get(i: word): pttype;
    function Put(i: word; T: ttype): boolean;

    function Concat(var a: tarray): boolean;
  end;

constructor TArray.init(sz: word);
  begin
    SetSize(sz);
    arr := Allocate(SizeOfArray)
  end;

destructor TArray.done;
  begin
    DeAllocate(GetSize);
  end;


function TArray.first: word;
  begin
    first := low(arr^)
  end;
function TArray.last: word;
  begin
    last := GetSize
  end;


function TArray.ValidIndex(i: word): boolean;
  begin
    ValidIndex := ((i > 0) and (i <= GetSize))
  end;


function TArray.Concat(var a: TArray): boolean;
  var mySize, newSize: word;
  begin
    Concat := False; (* concat of arrays is too long *)
    newSize := GetSize + a.GetSize;
    if newSize > (2 * maxint div sizeof(ttype))
      then exit;

    mySize := GetSize;
    Resize(newSize);
    move(a.arr^, arr^[mySize + 1],
         a.GetSize * SizeOf(TType));
    a.Done;
  end;

(*
  Private procedures & functions
*)
Function TArray.Allocate(sz: Word): PArrType;
  Var p: PArrType;
  Begin
    GetMem(p, sz * SizeOf(TType));
    Allocate := p
  End;

Procedure TArray.DeAllocate(sz: Word);
  Begin
    FreeMem(arr, sz * SizeOf(TType));
    arr := nil
  End;

Procedure TArray.Swap(i, j: Word);
  Var
    T: TType;
  Begin
    T := arr^[i]; arr^[i] := arr^[j]; arr^[j] := T
  End;

Procedure TArray.Sort(n, t: Word);
  Begin

    While (
        (t shl 1+1 <= n) and
          (arr^[t shl 1+1] > arr^[t])
      or
        (t shl 1 <= n) and
          (arr^[t shl 1] > arr^[t])
      ) Do
      Begin
        If
            (arr^[t shl 1+1] >= arr^[t shl 1])
          and (t shl 1 +1 <= n) then

          Begin
            swap(Succ(t shl 1), t);
            t := Succ(t shl 1)
          End
        Else
          Begin
            swap(t shl 1, t);
            t := t shl 1
          End
      End;
  End;


(*
  Public procedures & functions
*)
Function TArray.Get(i: Word): PTType;
  Begin

    If ValidIndex(i) Then Get := @(arr^[i])
    Else Get := nil

  End;

Function TArray.Put(i: Word; T: TType): boolean;
  Begin
    Put := true;

    If ValidIndex(i) Then
      arr^[i] := T
    else Put := false

  End;


Procedure TArray.Resize(sz: Word);
  Var p: PArrType;
  Begin
    If sz <= GetSize Then Exit;

    p := Allocate(sz);
    FillChar(p^, sz * SizeOf(TType), 0);
    move(arr^, p^, GetSize * SizeOf(TType));
    DeAllocate(GetSize);
    SetSize(sz); arr := p
  End;

Function TArray.GetSize: Word;
  Begin
    GetSize := SizeOfArray
  End;

Procedure TArray.SetSize(sz: Word);
  Begin
    SizeOfArray := sz
  End;

Procedure TArray.HSort;
  Var
    i: Word;
  Begin
    For i := SizeOfArray DownTo 1 Do
      Sort( SizeOfArray, i );
    For i := SizeOfArray Downto 1 Do
      Begin
        Swap(1, i); sort(i-1, 1)
      End;
  End;


Procedure TArray.qSort(Left, Right: Integer);
  Var
    l, r: Integer;
    B: TType;
  Begin
    l := left; r := right;
    B := arr^[l];
    Repeat
      While
          (arr^[r] >= B)
        and (l<r) Do Dec(r);
      arr^[l]:=arr^[r];

      While
          (arr^[l] <= B)
        and (l<r) Do Inc(l);
      arr^[r]:=arr^[l];
    Until r=l;

    arr^[l] := B;
    If Left < Pred(L) Then qSort(Left, Pred(l));
    If Succ(r) < Right Then qSort(Succ(r),Right)
  End;


Function TArray.max: PTType;
  Var max_ix, i: Word;
  Begin
    max_ix := 1;
    For i := 2 To GetSize Do
      If
          arr^[i] > arr^[max_ix]
        Then max_ix := i;
    max := @(arr^[max_ix])
  End;

Function TArray.min: PTType;
  Var min_ix, i: Word;
  Begin
    min_ix := 1;
    for i := 2 to GetSize do
      if
          arr^[i] < arr^[min_ix]
        then min_ix := i;
    min := @(arr^[min_ix])
  End;

Function TArray.maxIndex: Word;
  Begin
    maxIndex := IndexOf(max^)
  End;

Function TArray.minIndex: Word;
  Begin
    minIndex := IndexOf(min^)
  End;

Function TArray.IndexOf(T: TType): Word;
  Var
    i: Word; Ent: Boolean;
  Begin
    IndexOf := 0;

    i := 1; Ent := False;
    While (i <= SizeOfArray) and (not Ent) Do
      Begin
        if
            arr^[i] = T
        then
          Begin Ent := True; IndexOf := i End;
        Inc(i, 1)
      End
  End;

Procedure TArray.Invert;
  Var i: Word;
  Begin
    For i := 1 To (SizeOfArray div 2) Do
      Swap(i, Succ(SizeOfArray - i))
  End;


(*
  Return values:
  -1: cannot create file
*)
Function TArray.Print(s: String): Integer;
  Var
    f: Text; i: Word;
  Begin
    Assign(f, s);
    {$i-} ReWrite(f); {$i+}
    Print := -1;
    If IOResult <> 0
      Then Exit;

    For i := 1 To GetSize Do
      write(f, Get(i)^, ' ');

    Write(f, nLine);
    Print := GetSize;
    Close(f)
  End;

(*
  Return values:
  -1: file not found
*)
Function TArray.Input(n: Integer;
         s: String): Integer;
  Var
    i, WasRead: Integer;
    T: TType;
    f: Text;
  Begin
    Assign(f, s);
    {$I-} Reset(f); {$I+}
    Input := -1;
    If IOResult <> 0
      Then Exit;

    WasRead := 0;
    For i := 1 to n Do
      Begin
        If (s <> '') and SeekEOF(f) Then Break;
        ReadLn(f, T);
        Inc(WasRead);
        Put(WasRead, T)
      End;

    Input := WasRead;
    Close(f)
  End;