SPSEQ - Sequences
Tác giả: ladpro98
Ngôn ngữ: Pascal
program spseq;
uses math;
const fi='';
maxN=100005;
var a,b,lis,lis2,f:array[0..maxn] of longint;
n,res,i:longint;
procedure input;
var f:text;
i:longint;
begin
assign(f,fi);
reset(f);
readln(f,n);
for i:=1 to n do
read(f,a[i]);
close(f);
b:=a;
end;
function findmax(r,key:longint):longint;
var l,m,k:longint;
begin
l:=0;k:=0;
while l<=r do
begin
m:=(l+r) shr 1;
if a[f[m]]<key then
begin
k:=m;
l:=m+1;
end
else
r:=m-1;
end;
exit(k);
end;
procedure dp;
var i,d,x:longint;
begin
lis[1]:=1;
f[1]:=1;
d:=1;
for i:=2 to n do
begin
if a[i]<a[f[1]] then
begin
lis[i]:=1;
f[1]:=i
end
else
begin
if a[i]>a[f[d]] then
begin
inc(d);
f[d]:=i;
lis[i]:=d;
end
else
begin
X:=findmax(d,a[i])+1;
f[x]:=i;
lis[i]:=x;
end;
end;
end;
end;
begin
input;
dp;
for i:=1 to n do lis2[i]:=lis[n-i+1];
for i:=1 to n do a[i]:=b[n-i+1];
dp;
for i:=1 to n do
res:=max(res,min(lis[i],lis2[i])*2-1);
write(res);
end.