const
	maxn=50005;
	maxm=1000005;
var
	x,next,bite:array[0..maxn]of longint;
	y:array[0..maxm]of longint;
	ans:array[0..4*maxn]of longint;
	z:array[0..4*maxn,1..3]of longint;
	i,j,k:longint;
	n,m:longint;
procedure sort(l,r:longint);
var i,j,a,b:longint;
begin
	i:=l; j:=r; a:=z[(l+r)>>1,1];
	repeat
		while (z[i,1]<a) do inc(i);
		while (a<z[j,1]) do dec(j);
		if not (i>j) then 
		begin
			b:=z[i,1]; z[i,1]:=z[j,1]; z[j,1]:=b;
			b:=z[i,2]; z[i,2]:=z[j,2]; z[j,2]:=b;
			b:=z[i,3]; z[i,3]:=z[j,3]; z[j,3]:=b;
			inc(i); dec(j);
		end;
	until i>j;
	if (l<j) then sort(l,j);
	if (i<r) then sort(i,r);
end;

procedure update(a,b:longint);
begin
	while (a<=n) do
	begin
		inc(bite[a],b);
		inc(a,a and (-a));
	end;
end;

function query(a:longint):longint;
var sum:longint;
begin
	sum:=0;
	while (a>0) do
	begin
		inc(sum,bite[a]);
		dec(a,a and (-a));
	end;
	exit(sum);
end;

begin
	assign(input,'diff.in'); assign(output,'diff.out'); reset(input); rewrite(output);
	readln(n);
	for i:=1 to n do read(x[i]);
	fillchar(y,sizeof(y),0);
	fillchar(bite,sizeof(bite),0);
	fillchar(next,sizeof(next),0);
	for i:=1 to n do
	begin
		if (y[x[i]]<>0) then next[y[x[i]]]:=i else update(i,1);
		y[x[i]]:=i;
	end;
	readln(m);
	for i:=1 to m do begin readln(z[i,1],z[i,2]); z[i,3]:=i; end;
	sort(1,m); {z[i,1]}
	z[0,1]:=1;
	for i:=1 to m do
	begin
		for j:=z[i-1,1] to z[i,1]-1 do
		begin update(j,-1); if (next[j]<>0) then update(next[j],1); end;
		ans[z[i,3]]:=query(z[i,2])-query(z[i,1]-1);	
	end;
	for i:=1 to m do writeln(ans[i]);
	close(input); close(output);
end.