Wavio Sequence
Wavio数列由一连串的整数构成的。他有一些有趣的特性。
- 他的长度一定是奇数，也就是 L= 2*n+1
- 在Wavio数列中的前 n+1个整数为严格递增。
- 在Wavio数列中的后 n+1个整数为严格递减。
- 在Wavio数列中没有相邻的2个数是一样的。
例如：1, 2, 3, 4, 5, 4, 3, 2, 0是一个长度为 9 的Wavio数列。但是1, 2, 3, 4, 5, 4, 3, 2, 2不是一个Wavio数列。在这个问题中，给你一连串的整数，请你找出在这些整数中你可以找到的一个子字串为Wavio数列的最大长度是多少？例如在以下一连串的整数：
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1
最长的Wavio数列是：1 2 3 4 5 4 3 2 1，所以应该输出 9。
Input Wavio.in
输入含有多组测试资料
每组测试资料以1个正整数N（1 <= N <= 10000）开始，代表给你整数的数目。从下一列开始有N个整数。请参考Sample Input。
Output Wavio.out
对每组测试资料请输出一列 。在输入的一连串的整数，请你找出在这些整数中你可以找到的Wavio数列最大的长度是多少。
|
Sample Input |
Sample Output |
|
10
1 2 3 4 5 4 3 2 1 10
19
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1
5
1 2 3 4 5
20
13 7 5 7 6 7 2 7 3 20 9 9 15 20 9 10 12 12 4 13 |
9
9
1
7 |
Program Wavio_Mpq;
Const Maxn=10000;
type data=array[0..Maxn] of integer;
var
n:integer;
a,f,up,down:data;
procedure init;
var
i:integer;
begin
readln(n);
for i:=1 to n do read(a[i]);
readln;
end;
function Lis(var ans:data):data;
var
i,m,min,max,len:integer;
begin
len:=0;
fillchar(f,sizeof(f),0);
for i:=1 to n do
begin
min:=1; max:=len;
while min<=max do
begin
m:=(Min+Max) div 2;
if f[m]<a[i] then min:=m+1 else
if f[m]>a[i] then max:=m-1 else
begin
min:=m;
break;
end;
end;
f[min]:=a[i];
if min>len then len:=min;
ans[i]:=min;
end;
exit(ans);
end;
function Min(a,b:integer):integer;
begin
if a<b then exit(a) else exit(b);
end;
function Max(a,b:integer):integer;
begin
if a>b then exit(a) else exit(b);
end;
procedure Dp;
var
i,answer:integer;
begin
up:=Lis(up);
for i:=1 to n div 2 do
begin
a[0]:=a[i];
a[i]:=a[n-i+1];
a[n-i+1]:=a[0];
end;
down:=Lis(down);
answer:=0;
for i:=1 to n do
answer:=Max(2*Min(up[i],down[n-i+1])-1,answer);
writeln(answer);
end;
begin
assign(input,'Wavio.in'); reset(input);
assign(output,'Wavio.out'); rewrite(output);
while Not eof do
begin
init;
Dp;
end;
close(input); close(output);
end.