var a,b,bb:array[1..50001]of longint;
 c:array[1..50001,1..4]of int64;
 qq,q,ww,n,h,t,tt:longint;
 i,j:longint;
 ans:int64;
 summ:array[1..100]of int64;
 ss:string;

 procedure o(s:int64);
 var i:longint;
  t,k:array[1..52]of int64;
  begin
  i:=0;
  fillchar(k,sizeof(k),0);
  fillchar(t,sizeof(t),0);
  while s>0 do
  begin
  inc(i);
  k[i]:=s mod 10;
  s:=s div 10;
  end;
  for i:=1 to 50 do
  begin
  t[i]:=t[i]+summ[i]+k[i];
  if t[i]>=10 then
   begin
   t[i+1]:=t[i+1]+t[i] div 10;
   t[i]:=t[i] mod 10;
   end;
   summ[i]:=t[i];
  end;
  end;



 procedure cc(x,k:longint;w:int64);
  begin
  while k<50001 do
  begin
  inc(c[k,x],w);
  inc(k,k and (-k));
  end;
  end;

 function sum(x,k:longint):int64;
  begin
  sum:=0;
  while k>0 do
   begin
   inc(sum,c[k,x]);
   dec(k,k and(-k));
   end;
  end;

 procedure kp(l,r:longint);
 var i,j,t,m:longint;
  begin
  i:=l;
  j:=r;
  m:=a[(l+r)>>1];
  repeat
  while b[a[i]]<b[m] do inc(i);
  while b[a[j]]>b[m] do dec(j);
  if i<=j then
   begin
   t:=a[i];
   a[i]:=a[j];
   a[j]:=t;
   inc(i);
   dec(j);
   end;
 until i>j;
 if i<r then kp(i,r);
 if j>l then kp(l,j);
 end;

 begin
while not eof do
begin
 fillchar(bb,sizeof(bb),0);
  fillchar(c,sizeof(c),0);
 fillchar(summ,sizeof(summ),0);
 fillchar(a,sizeof(a),0);
 fillchar(b,sizeof(b),0);
 readln(n);
  for i:=1 to n do
 begin
 read(b[i]);
 a[i]:=i;
 end;
 kp(1,n);

 bb[a[1]]:=1;

 qq:=1;
 for i:=2 to n do
 if b[a[i]]>b[a[i-1]] then
 begin
 inc(qq);
 bb[a[i]]:=qq;
 end
 else
 bb[a[i]]:=qq;
 for i:=1 to n do
  begin
  cc(1,bb[i],1);
  for j:=2 to 4 do
  begin
  ans:=sum(j-1,bb[i]-1);
  cc(j,bb[i],ans);
  end;
  ans:=sum(4,bb[i]-1);
  o(ans);
  end;



  for i:=50 downto 1 do
  if summ[i]<>0 then break;
  for i:=i downto 1 do
  write(summ[i]);
  writeln;
end;
end.