program Project1;

type
  TData = record
  	x, i: integer;
  end;

  TDec = record
	head: dword;
    tail: dword;
    size: dword;
    maxsize: dword;
    data: array of TData;
  end;

procedure Create_Dec(var d: TDec; maxsize: dword);
begin
  	SetLength(d.data, maxsize);
  	d.size := 0;
  	d.tail := 0;
  	d.head := 0;
    d.maxsize := maxsize;
end;

function Push_Dec(var d: TDec; data: TData): boolean;
begin
	d.data[(d.head + d.size) mod d.maxsize] := data;
    d.size += 1;
    if (d.size = 1) then
    	d.tail := d.head
    else
    	d.tail += 1;

end;
function Pop_head(var d:TDec): boolean;
begin
    d.head += 1;
	if (d.head > d.maxsize) then begin
    	d.head := 0;
    end;
    d.size -= 1;

end;

function Pop_tail(var d:TDec): boolean;
begin
	if (d.tail < 0) then begin
		d.tail := d.maxsize-1;
    end;
    d.size -= 1;
    d.tail -= 1;
end;

function Del_dec(var d:TDec): boolean;
begin
	if (d.size > 0) then begin
        finalize(d.data);
    end else begin
      exit(false);
    end;
end;

type
  TArray  = array of integer;

procedure Find_max(n, k: integer; arr: TArray);

var d:TDec;
  data: TData;
  i: integer;
  num: Tdata;
begin
	Create_dec(d, n);
    data.x := arr[1];
    data.i := 1;
    Push_dec(d, data);
    write(data.x, ' ');
    for i:=2 to n do begin
   		num.x := arr[i];
        num.i := i;
        while (d.size > 0) and (d.data[d.tail].x < num.x) do begin
        	Pop_tail(d);
        end;
        Push_dec(d, num);
        if (d.data[d.head].i < i-k) then begin
        	Pop_head(d);
        end;
        write(d.data[d.head].x, ' ');
    end;
end;
procedure Find_min(n, k: integer; arr: TArray);
var d:TDec;
  data: TData;
  i: integer;
  num: Tdata;
begin
	Create_dec(d, n);
    data.x := arr[1];
    data.i := 1;
    Push_dec(d, data);
    write(data.x, ' ');
    for i:=2 to n do begin
   		num.x := arr[i];
        num.i := i;
        while (d.size > 0) and (d.data[d.tail].x > num.x) do begin
        	Pop_tail(d);
        end;
        Push_dec(d, num);
        if (d.data[d.head].i < i-k) then begin
        	Pop_head(d);
        end;
        write(d.data[d.head].x, ' ');
    end;
end;

var
  k, n, i: integer;
  arr: array of integer;
begin
    assign(input, 'input2.txt');
    assign(output, 'output.txt');
    reset(input);
    rewrite(output);
    SetLength(arr, 1000000);
    for i := 0 to 1000000- 1 do begin
        arr[i] := random(100);
    end;
    k := 3;
    //readln(n, k);
    //SetLength(arr, n);
    //for i:=1 to n do begin
    //	read(arr[i]);
    //end;
    Find_max(1000000 - 1, 100000, arr);
    writeln;
    writeln;
    writeln;
    writeln;
    writeln;

    Find_min(1000000 - 1, 100000+, arr);
end.