我们按照询问的右端点排序，然后对于每一个位置，记录同颜色
上一个出现的位置，每次将上上位置出现的+1，上次出现的-1，然后
用树状数组维护就好了
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/
//By BLADEVIL
var
n, m, t, l :longint;
pre, other, num :array[..] of longint;
last, ans, first, a, pred, c :array[..] of longint;
procedure connect(x,y,tot:longint);
begin
inc(l);
pre[l]:=last[x];
last[x]:=l;
other[l]:=y;
num[l]:=tot;
end;
procedure add(x,y:longint);
begin
while (x<=n) do
begin
inc(c[x],y);
x:=x+(x and -x);
end;
end;
function ask(x:longint):longint;
var
sum :longint;
begin
sum:=;
while x> do
begin
sum:=sum+c[x];
x:=x-(x and -x);
end;
exit(sum);
end;
procedure init;
var
i, j :longint;
x, y :longint;
begin
readln(n,t,m);
for i:= to n do
begin
read(a[i]);
if first[a[i]]<> then pred[i]:=first[a[i]];
first[a[i]]:=i;
end;
for i:= to m do
begin
readln(x,y);
connect(y,x,i);
end;
end;
procedure main;
var
i :longint;
q, p :longint;
begin
for i:= to n do
begin
add(pred[pred[i]]+,);
add(pred[i]+,-);
q:=last[i];
while q<> do
begin
p:=other[q];
ans[num[q]]:=ask(p);
q:=pre[q];
end;
end;
for i:= to m do writeln(ans[i]);
end;
begin
init;
main;
end.