var a,b:array[1..10000] of integer;
c:array[1..3,1..10000] of integer;
k,i,j,m,n,p,l:integer;
begin
readln(n);
for i:=1 to n do
begin
read(a[i]);
c[1,i]:=a[i];
c[2,i]:=1; c[3,i]:=0;
end;
for i:=n-1 downto 1 do
begin
l:=0; m:=0;
for j:=i+1 to n do
if (c[1,j]<c[1,i]) and (c[2,j]>l) then
begin
l:=c[2,j];
m:=j;
end;
if l>0 then
begin
c[2,i]:=l+1;
c[3,i]:=m;
end;
end;
m:=1;
for j:=1 to n do
if c[2,i]<c[2,m] then m:=j;
while m<>0 do
begin
write(c[1,m],' ');
m:=c[3,m];
end;
k:=1; b[1]:=a[1];
for i:=2 to n do
begin
p:=0;
for j:=1 to k do
if b[j]>a[i] then
if p=0 then p:=j
else if b[j]<b[p] then p:=j;
if p=0 then
begin
inc(k);
b[k]:=a[i];
end
else b[p]:=a[i];
end;
write(k);
readln;
end.
var a,b:array[1..10000] of integer;
c:array[1..3,1..10000] of integer;
k,i,j,m,n,p,l,s:integer;
begin
readln(n);
for i:=1 to n do
begin
read(a[i]);
c[1,i]:=a[i];
c[2,i]:=1; c[3,i]:=0;
end;
for i:=n-1 downto 1 do
begin
l:=0; m:=0;
for j:=i+1 to n do
if (c[1,j]<c[1,i]) and (c[2,j]>l) then
begin
l:=c[2,j];
m:=j;
end;
if l>0 then
begin
c[2,i]:=l+1;
c[3,i]:=m;
end;
end;
m:=1;
for j:=1 to n do
if c[2,j]>c[2,m] then m:=j;
s:=0;
while m<>0 do
begin
inc(s);
// write(c[1,m]:4);
m:=c[3,m];
end;
k:=1; b[1]:=a[1];
for i:=2 to n do
begin
p:=0;
for j:=1 to k do
if b[j]>a[i] then
if p=0 then p:=j
else if b[j]<b[p] then p:=j;
if p=0 then
begin
inc(k);
b[k]:=a[i];
end
else b[p]:=a[i];
end;
write(s,' ',k);
readln;
end.