var i,j,n,maxlong,tail,minheight,select:longint;

h,longest,sys:array[1..maxn] of longint;

begin

readln(n);

for i:=1 to n do read(h[i]);

readln;

longest[1]:=1;

for i:=2 to n do

begin

maxlong:=1;

for j:=1 to i-1 do

if h[i]<=h[j] then

if longest[j]+1>maxlong then maxlong:=longest[j]+1;

longest[i]:=maxlong;

end;

maxlong:=longest[1];

for i:=2 to n do

if longest[i]>maxlong then maxlong:=longest[i];

write(maxlong,' ');

sys[1]:=h[1];

tail:=1;

for i:=2 to n do

begin

minheight:=maxint;

for j:=1 to tail do

if sys[j]>h[i] then

if sys[j]<minheight then begin

minheight:=sys[j];

select:=j

end;

if minheight=maxint

then begin

tail:=tail+1;

sys[tail]:=h[i];

end

else sys[select]:=h[i];

end;

write(tail);

end.