## Editorial for Sequences

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
fo='';
maxn=100001;
type ar=array[0..maxn] of longint;
var n,re,num,max:longint;
a,d,e,f,inc,dec:ar;

procedure rf;
var i:longint;
begin
assign(input,fi); reset(input);
for i:=1 to n do
begin
d[i]:=i;
end;
close(input);
end;

procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l; j:=r; x:=a[(i+j) shr 1];
repeat
while a[i]<x do i:=i+1;
while a[j]>x do j:=j-1;
if i<=j then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
y:=d[i]; d[i]:=d[j]; d[j]:=y;
i:=i+1; j:=j-1;
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;

procedure edit;
var i:longint;
begin
a[0]:=-1;
for i:=1 to n do
begin
e[d[i]]:=i;
if a[i]=a[i-1] then d[i]:=d[i-1]
else d[i]:=d[i-1]+1;
end;
max:=d[n];
end;

function getmax(x,y:longint):longint;
begin
if x>y then getmax:=x else getmax:=y;
end;

begin
while x<=max do
begin
if f[x]<t then f[x]:=t else exit;
x:=x+x and (-x);
end;
end;

function calc(x:longint):longint;
var r:longint;
begin
r:=0;
while x>0 do
begin
r:=getmax(r,f[x]);
x:=x-x and (-x);
end;
calc:=r;
end;

procedure pr;
var i,x,t:longint;
begin
sort(1,n);
edit;
for i:=1 to n do
begin
x:=d[e[i]];
t:=calc(x-1);
inc[i]:=t+1;
end;
fillchar(f,sizeof(f),0);
for i:=n downto 1 do
begin
x:=d[e[i]];
t:=calc(x-1);
dec[i]:=t+1;
end;
re:=0;
for i:=1 to n do
begin
if inc[i]<dec[i] then t:=inc[i] shl 1-1
else t:=dec[i] shl 1-1;
if t>re then re:=t;
end;
end;

procedure wf;
begin
assign(output,fo); rewrite(output);
writeln(re);
close(output);
end;

begin
rf;
pr;
wf;
end.


#### Code mẫu của happyboy99x

#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;

#define N 100000

int x[N+1], a[N], n, lis[N], lds[N];

void LIS() {
fill(x+1, x+n+1, INT_MAX);
x[0] = INT_MIN; int maxlen = 0;
for(int i = 0; i < n; ++i) {
int p = lower_bound(x, x+maxlen+1, a[i]) - x;
lis[i] = p;
maxlen = max(maxlen, p);
x[p] = min(x[p], a[i]);
}
}

void LDS() {
fill(x+1, x+n+1, INT_MAX);
x[0] = INT_MIN; int maxlen = 0;
for(int i = n-1; i >= 0; --i) {
int p = lower_bound(x, x+maxlen+1, a[i]) - x;
lds[i] = p;
maxlen = max(maxlen, p);
x[p] = min(x[p], a[i]);
}
}

bool enter() {
if(scanf("%d", &n) == EOF) return 0;
for(int i = 0; i < n; ++i) scanf("%d", a+i);
return 1;
}

void print() {
int res = 0;
for(int i = 0; i < n; ++i) res = max(res, 2*min(lis[i], lds[i]) - 1);
printf("%d\n", res);
}

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
while(enter()) {
LIS(); LDS();
print();
}
return 0;
}


#### Code mẫu của ladpro98

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);
for i:=1 to n do
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.


#### Code mẫu của RR

//Written by RR

{$MODE OBJFPC} uses math; const FINP = ''; FOUT = ''; MAXN = 100111; var f1,f2 : text; n,s : longint; a,ind,c : array[1..MAXN] of longint; f,g : array[1..MAXN] of longint; ln : array[1..MAXN] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,n); for i:=1 to n do read(f1,a[i]); end; procedure swap(var a,b:longint); var tmp:longint; begin tmp:=a; a:=b; b:=tmp; end; procedure sort(l,r:longint); var i,j,mid:longint; begin i:=l; j:=r; mid:=c[l+random(r-l+1)]; repeat while c[i]<mid do inc(i); while c[j]>mid do dec(j); if i<=j then begin swap(c[i],c[j]); swap(ind[i],ind[j]); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<J then sort(l,j); end; procedure RR; var i:longint; begin for i:=1 to n do begin c[i]:=a[i]; ind[i]:=i; end; sort(1,n); a[ind[1]]:=1; s:=1; for i:=2 to n do begin if c[i]>c[s] then begin inc(s); c[s]:=c[i]; end; a[ind[i]]:=s; end; end; function get(u:longint):longint; var v:longint; begin if (u<=0) then exit(0); v:=u-u and (-u); exit(max(ln[u],get(v))); end; procedure update(u,k:longint); var v:longint; begin ln[u]:=max(ln[u],k); v:=u+u and (-u); if v<=s then update(v,k); end; procedure solve; var i,res:longint; begin for i:=1 to n do begin f[i]:=get(a[i]-1)+1; update(a[i],f[i]); end; fillchar(ln,sizeof(ln),0); for i:=n downto 1 do begin g[i]:=get(a[i]-1)+1; update(a[i],g[i]); end; res:=0; for i:=1 to n do res:=max(res,min(f[i],g[i])*2-1); writeln(f2,res); end; begin openF; inp; RR; solve; closeF; end.  #### Code mẫu của hieult #include <iostream> #include <cstdio> #include <cstdlib> #include <map> #include <set> #include <vector> #include <cmath> #include <cstring> #include <string> #include <algorithm> //#include <conio.h> using namespace std; #define REP(i,a,b) for(int i=a;i<=b;++i) #define DOWN(i,a,b) for(int i=a;i>=b;--i) #define FOR(i,a) REP(i,0,a); #define pb push_back #define INF 1000000000 #define VI vector<int> #define VVI vector<VI> //ham template <class T> //so ko am T gcd(T a, T b){if(b==0) return abs(a); else return gcd(b,a%b);} template <class T> T lcm(T a, T b){ return a/gcd(a,b) *b;} int n,a[100005],b[100005],l[100005],r[100005],m[100005],dis; int main() { //freopen("SPSEQ.IN", "rt", stdin); //freopen("SPSEQ.OUT", "wt", stdout); scanf("%d",&n); REP(i,0,n-1) { scanf("%d",&a[i]); //cout<<a[i]<<" "; b[n-1-i]=a[i]; } // cout<<endl; //Tinh left REP(i,0,n) m[i]=100005; //fill; dis=1; m[1]=a[0]; l[0]=1; REP(i,1,n-1) { if(m[1]>=a[i]) { l[i]=1; m[1]=a[i]; continue; } if(m[dis]<a[i]) { l[i]=dis+1; m[dis+1]=a[i]; dis++; continue; } int first=1,last=dis; while(last-1>first) { int mid=(first+last)/2; if(m[mid]<a[i]) first=mid; else //m[mid]>=a[i] { last=mid; } } l[i]=last; m[last]=a[i]; } /* REP(i,0,n-1) cout<<i<<" "<<l[i]<<endl; */ //return 0; //cout<<"Xong +_________________+"<<endl<<endl; //Tinh right REP(i,0,n) m[i]=100005; //fill; dis=1; m[1]=b[0]; r[n-1]=1; REP(i,1,n-1) { if(m[1]>=b[i]) { r[n-1-i]=1; m[1]=b[i]; continue; } if(m[dis]<b[i]) { r[n-1-i]=dis+1; m[dis+1]=b[i]; dis++; continue; } int first=1,last=dis; while(last-1>first) { int mid=(first+last)/2; if(m[mid]<b[i]) first=mid; else //m[mid]>=a[i] { last=mid; } } r[n-1-i]=last; m[last]=b[i]; } /* REP(i,0,n-1) cout<<i<<" "<<r[i]<<endl; */ int maxDis=-1; REP(i,0,n-1) { maxDis=max(maxDis,min(l[i],r[i])); } if(maxDis==0) cout<<"0"; else cout<<2*maxDis-1; }  #### Code mẫu của ll931110 {$MODE DELPHI}
program SPSEQ;
const
input  = '';
output = '';
maxn = 100000;
var
a,b,d,pos: array[1..maxn] of integer;
L,L1,L2,t: array[1..maxn] of integer;
n: integer;
res: integer;

procedure init;
var
f: text;
i: integer;
begin
assign(f, input);
reset(f);

for i := 1 to n do
begin
pos[i] := i;
end;

close(f);
end;

procedure swap(var x,y: integer);
var
z: integer;
begin
z := x;  x := y;  y := z;
end;

procedure swapint(i,j: integer);
begin
swap(d[i],d[j]);
swap(pos[i],pos[j]);
end;

procedure quicksort;

procedure par(l,h: integer);
var
i,j,p: integer;
begin
if l >= h then exit;
i := l;  j := h;  p := d[random(h - l + 1) + l];

repeat
while (d[i] < p) do inc(i);
while (d[j] > p) do dec(j);

if i <= j then
begin
if i < j then swapint(i,j);
inc(i);
dec(j);
end;
until i > j;

par(l,j);
par(i,h);
end;

var
i,c: integer;
begin
par(1,n);
c := 1;
b[pos[1]] := 1;
for i := 2 to n do
begin
if d[i] > d[i - 1] then inc(c);
b[pos[i]] := c;
end;
end;

procedure update(x,m: integer);
begin
while x <= maxn do
begin
if t[x] < m then t[x] := m;
x := x + (x and -x);
end;
end;

function calc(x: integer): integer;
var
r: integer;
begin
r := 0;
while x > 0 do
begin
if r < t[x] then r := t[x];
x := x - (x and -x);
end;
calc := r;
end;

procedure optimize;
var
i: integer;
begin
fillchar(t, sizeof(t), 0);

update(1,1);
for i := 1 to n do
begin
L[i] := calc(a[i]);
update(a[i] + 1,L[i] + 1);
end;
end;

procedure solve;
var
i,min: integer;
begin
for i := 1 to n do a[i] := b[i];
optimize;
L1 := L;

for i := 1 to n do a[i] := b[n + 1 - i];
optimize;
L2 := L;

res := 0;
for i := 1 to n do
begin
if L1[i] > L2[n + 1 - i] then min := L2[n + 1 - i] else min := L1[i];
if res < min then res := min;
end;
end;

procedure printresult;
var
f: text;
begin
assign(f, output);
rewrite(f);
writeln(f, 2 * res - 1);
close(f);
end;

begin
init;
quicksort;
solve;
printresult;
end.


#### Code mẫu của khuc_tuan

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int n;
int a[100010], f1[100010], f2[100010], g[100010];

void process( int * a, int * f) {
int ng = 0;
for(int i=0;i<n;++i) {
int id = lower_bound( g, g + ng, a[i]) - g;
if(id == ng) ++ng;
g[id] = a[i];
f[i] = ng;
}
}

int main() {
scanf("%d", &n);
for(int i=0;i<n;++i) scanf("%d", a+i);
process( a, f1);
reverse( a, a + n);
process( a, f2);
int best = 0;
for(int i=0;i<n;++i) best = max( best, min(f2[i], f1[n-i-1]) * 2 - 1);
cout << best << endl;
return 0;
}