ZZXYY's blog

{$inline on}
var
  a:array[0..50000,1..3] of longint;
  t,y,p,ans:array[1..50000] of longint;
  n,m,i,j,k,block,l,r:longint;
procedure sort(l,r:longint);
var
  i,j,x,y:longint;
begin
  i:=l;
  j:=r;
  x:=a[(l+r) div 2,1];
  repeat
    while a[i,1]<x do
    inc(i);
    while x<a[j,1] do
    dec(j);
    if not(i>j) then
    begin
      a[0]:=a[i];
      a[i]:=a[j];
      a[j]:=a[0];
      inc(i);
      j:=j-1;
    end;
  until i>j;
  if l<j then
  sort(l,j);
  if i<r then
  sort(i,r);
end;
procedure sort2(l,r:longint);
var
  i,j,x,y,k:longint;
begin
  i:=l;
  j:=r;
  x:=p[a[(l+r) div 2,1]];
  y:=a[(l+r) div 2,2];
  repeat
    while (p[a[i,1]]<x) or (p[a[i,1]]=x) and (a[i,2]<y) do
    inc(i);
    while (x<p[a[j,1]]) or (x=p[a[j,1]]) and (y<a[j,2]) do
    dec(j);
    if not(i>j) then
    begin
      a[0]:=a[i];
      a[i]:=a[j];
      a[j]:=a[0];
      inc(i);
      j:=j-1;
    end;
  until i>j;
  if l<j then
  sort2(l,j);
  if i<r then
  sort2(i,r);
end;
function lb(x:longint):longint; inline;
begin
  exit(x and -x);
end;
procedure change(x,k:longint); inline;
var
  i:longint;
begin
  i:=x;
  while i<=n do
  begin
    t[i]:=t[i]+k;
    i:=i+lb(i);
  end;
end;
function query(x:longint):longint;   inline;
var
  i,ans:longint;
begin
  i:=x;
  ans:=0;
  while i>0 do
  begin
    ans:=ans+t[i];
    i:=i-lb(i);
  end;
  exit(ans);
end;
begin
  read(n);
  block:=trunc(sqrt(n));
  for i:=1 to n do
  begin
    read(a[i,1]);
    a[i,2]:=i;
    p[i]:=(i-1) div block;
  end;
  sort(1,n);
  for i:=1 to n do
  y[a[i,2]]:=i;
  read(m);
  for i:=1 to m do
  begin
    read(a[i,1],a[i,2]);
    a[i,3]:=i;
  end;
  sort2(1,m);
  k:=0;
  l:=1;
  r:=0;
  for i:=1 to m do
  begin
    if r<a[i,2] then
    for j:=r+1 to a[i,2] do
    begin
      inc(r);
      change(y[j],1);
      k:=k+r-l+1-query(y[j]);
    end;
    if r>a[i,2] then
    for j:=r downto a[i,2]+1 do
    begin
      change(y[j],-1);
      k:=k-(r-l-query(y[j]));
      dec(r);
    end;
    if l<a[i,1] then
    for j:=l to a[i,1]-1 do
    begin
      change(y[j],-1);
      k:=k-query(y[j]-1);
      inc(l);
    end;
    if l>a[i,1] then
    for j:=l-1 downto a[i,1] do
    begin
      dec(l);
      change(y[j],1);
      k:=k+query(y[j]-1);
    end;
    ans[a[i,3]]:=k;
  end;
  for i:=1 to m do writeln(ans[i]);
end.