NTSEQ - Số lượng dãy con tăng
Tác giả: RR
Ngôn ngữ: Pascal
uses math;
const
base=1000000007;
var
bit,ind,thutu,startof,sl,a,f,last:array[1..100111] of longint;
val,u,top,i,n:longint;
function find1(val:longint):longint;
var
l,r,mid,res:longint;
begin
l:=1; r:=top; res:=1;
while l<=r do
begin
mid:=(l+r) shr 1;
if last[mid]<val then
begin
res:=mid;
l:=mid+1;
end
else r:=mid-1;
end;
exit(res);
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,mf,ma,key:longint;
begin
i:=l; j:=r;
key:=l+random(r-l+1); mf:=f[key]; ma:=a[key];
repeat
while (f[i]<mf) or ((f[i]=mf) and (a[i]<ma)) do inc(i);
while (f[j]>mf) or ((f[j]=mf) and (a[j]>ma)) do dec(j);
if i<=j then
begin
swap(f[i],f[j]);
swap(a[i],a[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;
function find2(l,r,val:longint):longint;
var
res,mid:longint;
begin
res:=l;
while l<=r do
begin
mid:=(l+r) shr 1;
if a[mid]<val then
begin
res:=mid;
l:=mid+1;
end
else r:=mid-1;
end;
exit(res);
end;
function get(u:longint):longint;
var
tmp,v:longint;
begin
if u<=0 then exit(0);
v:=u-u and (-u);
tmp:=bit[u]+get(v);
if tmp>base then dec(tmp,base);
exit(tmp);
end;
procedure update(u,k:longint);
var
v:longint;
begin
bit[u]:=bit[u]+k;
if bit[u]>base then dec(bit[u],base);
v:=u+u and (-u);
if v<=n then update(v,k);
end;
begin
read(n);
for i:=1 to n do read(a[i]);
last[1]:=a[1]; f[1]:=1; top:=1;
for i:=2 to n do
if a[i]<=last[1] then
begin
f[i]:=1;
last[1]:=a[i];
end
else if a[i]>last[top] then
begin
f[i]:=top+1;
inc(top); last[top]:=a[i];
end
else
begin
u:=find1(a[i]);
f[i]:=u+1;
last[u+1]:=min(last[u+1],a[i]);
end;
for i:=1 to n do ind[i]:=i;
sort(1,n);
startof[1]:=1;
for i:=2 to n do
if f[i]>f[i-1] then
startof[f[i]]:=i;
for i:=1 to n do
thutu[ind[i]]:=i;
for i:=1 to n do
begin
u:=thutu[i];
if f[u]=1 then begin sl[u]:=1; update(u,sl[u]); continue; end;
val:=find2(startof[f[u]-1],startof[f[u]]-1,a[u]);
sl[u]:=get(val)-get(startof[f[u]-1]-1);
if sl[u]<0 then inc(sl[u],base);
update(u,sl[u]);
end;
val:=get(n)-get(startof[f[n]]-1);
if val<0 then inc(val,base);
writeln(val);
end.