NTSEQ - Số lượng dãy con tăng
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
maxn=100010;
z=1000000007;
var n,maxc,re,res:longint;
f,a,d,e,g:array[1..maxn] of longint;
procedure rf;
var i:longint;
begin
read(n);
for i:=1 to n do
begin
read(a[i]);
d[i]:=i;
end;
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
maxc:=1; e[d[1]]:=1;
for i:=2 to n do
begin
if a[i]<>a[maxc] then
begin
maxc:=maxc+1;
a[maxc]:=a[i];
end;
e[d[i]]:=maxc;
end;
end;
procedure add(x,val:longint);
begin
while x<=maxc do
begin
if val<f[x] then f[x]:=val
else exit;
x:=x+x and (-x);
end;
end;
function calc(x:longint;var val:longint):longint;
var r:longint;
begin
r:=0; val:=0;
while x>0 do
begin
if f[x]=r then
begin
val:=val+g[x];
if val>=z then val:=val-z;
end;
if f[x]>r then
begin
r:=f[x];
val:=g[x];
end;
x:=x-x and (-x);
end;
calc:=r;
end;
procedure update(x,t,u:longint);
begin
while x<=maxc do
begin
if t<f[x] then exit;
if t=f[x] then
begin
g[x]:=g[x]+u;
if g[x]>=z then g[x]:=g[x]-z;
end;
if t>f[x] then
begin
g[x]:=u;
f[x]:=t;
end;
x:=x+x and (-x);
end;
end;
procedure pr;
var i,t,u:longint;
begin
sort(1,n);
edit;
re:=0; res:=0;
for i:=1 to n do
begin
t:=calc(e[i]-1,u);
if u=0 then u:=1;
update(e[i],t+1,u);
end;
re:=calc(maxc,res);
writeln(res);
end;
begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.