记录编号	39328	评测结果	AAAAAAAAAA
题目名称	859.数列	最终得分	100
用户昵称	isabella	是否通过	通过
代码语言	Pascal	运行时间	0.043 s
提交时间	2012-07-09 12:04:40	内存使用	1.12 MiB

var
 n,i,j,temp:longint;
 ans:int64;
 a,b,num,nn,tot:array[0..50010]of longint;

 procedure guibing(l,r:longint);
 var
   i,j,mid,k:longint;
 begin
   if l=r then exit;
   mid:=(l+r)div 2;
   guibing(l,mid);
   guibing(mid+1,r);
   i:=l;
   j:=mid+1;
   k:=l;
   while(i<=mid)and(j<=r) do
     begin
       if a[i]>=a[j] then
         begin b[k]:=a[i];nn[k]:=num[i];inc(k);inc(i);end
        else begin
         b[k]:=a[j];nn[k]:=num[j];
         inc(nn[k],mid-i+1);
         inc(k);inc(j);
        end;
     end;

   while i<=mid do
    begin b[k]:=a[i];nn[k]:=num[i];inc(k);inc(i);end;
   while j<=r do
    begin b[k]:=a[j];nn[k]:=num[j];inc(k);inc(j);end;

   for i:=l to r do begin a[i]:=b[i];num[i]:=nn[i];end;
 end;

begin
assign(input,'queueb.in');reset(input);
assign(output,'queueb.out');rewrite(output);
 fillchar(num,sizeof(num),0);
 readln(n);
 for i:=1 to n do read(a[i]);
 guibing(1,n);

 i:=n;
 while i>=1 do
  begin
   temp:=n-i;
   j:=i;
   while a[j]=a[i]do begin tot[j]:=temp;dec(j);end;
   i:=j;
  end;
 ans:=0;
 for i:=1 to n do
  begin
   ans:=ans+num[i]*(tot[i]-num[i]);
  end;
 writeln(ans);

 {for i:=1 to n do write(a[i],' ');writeln;
 for i:=1 to n do write(tot[i],' ');writeln;
 for i:=1 to n do write(num[i],' ');writeln; }
close(input);close(output);
end.