像我这种蒟蒻这道题从在线算法思考基本毫无思路
但是发现题目中只涉及到询问而不涉及到修改，这类题目一般都是离线算法大概
考虑到这题为什么不能直接区间求值，因为区间中同色点会被重复计算（废话）
下面我们就要通过离线算法来排除区间内同色点干扰
首先想到对询问区间以左端点排序，
考虑到区间内的同色点我们只要算最左边的就行了
先将每种颜色第一次出现的位置标记为1
然后从左往右扫描每一个位置，算出以这个位置为左端点的区间答案（区间和）
然后再将这个位置颜色的下一个同色位置标记
这样我们就保证了每次区间询问，同色点只算了一遍
因为一个区间内要么不存在同色点，
要么同色点只出现了一次（被标记了一次），下一个同色点一定还没有标记，而上一个同色点一定在区间外左侧
语言表述不太好，具体还是看程序吧……
var a,c,next:array[..] of longint;
x,y,ans,p:array[..] of longint;
last:array[..] of longint;
max,i,n,m,j:longint;
function lowbit(x:longint):longint;
begin
exit(x and(-x));
end; function sum(x:longint):longint;
begin
sum:=;
while x<> do
begin
sum:=sum+c[x];
x:=x-lowbit(x);
end;
end; procedure add(x:longint);
begin
while x<=n do
begin
inc(c[x]);
x:=x+lowbit(x);
end;
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure sort(l,r: longint);
var i,j,z: longint;
begin
i:=l;
j:=r;
z:=x[(l+r) div ];
repeat
while x[i]<z do inc(i);
while z<x[j] do dec(j);
if not(i>j) then
begin
swap(x[i],x[j]);
swap(y[i],y[j]);
swap(p[i],p[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; begin
readln(n);
for i:= to n do
begin
read(a[i]);
if max<a[i] then max:=a[i];
end;
readln(m);
for i:= to m do
begin
readln(x[i],y[i]);
p[i]:=i;
end;
sort(,m);
fillchar(last,sizeof(last),);
for i:=n downto do //计算每个位置下一个同色点的位置
begin
next[i]:=last[a[i]];
last[a[i]]:=i;
end;
for i:= to max do //先映射每种颜色第一次出现的位置
if last[i]<> then add(last[i]); j:=;
for i:= to n do
begin
while x[j]=i do
begin
ans[p[j]]:=sum(y[j])-sum(x[j]-);
inc(j);
end;
if next[i]<> then add(next[i]);
end;
for i:= to m do
writeln(ans[i]);
end.