type tab=array[1..100001] of longint;
var a,b:text;
	t:tab;
	m,n,i,tip,p:longint;

function b0(s,f,p:longint):longint;
var mid:longint;
begin
	if s>f then b0:=-1 else
	begin
		mid:=((s+f) div 2) + ((s+f) mod 2);
		if (t[mid]=p) and (s<>f) then b0:=b0(mid,f,p) else if (s=f) then b0:=mid;
		if t[mid]<p then b0:=b0(mid+1,f,p);
		if t[mid]>p then b0:=b0(s,mid-1,p);
	end;
end;

function b1(s,f,p:longint):longint;
var mid:longint;
begin
	if s>f then b1:=-1 else
	begin
		mid:=((s+f) div 2) + ((s+f) mod 2);
		if (t[mid]<=p) and (s<>f) then b1:=b1(mid,f,p) else if (s=f) then b1:=mid;
		if t[mid]>p then b1:=b1(s,mid-1,p);
	end;
end;

function b2(s,f,p:longint):longint;
var mid:longint;
begin
	if s>f then b2:=-1 else
	begin
		mid:=((s+f) div 2);
		if (t[mid]>=p) and (s<>f) then b2:=b2(s,mid,p) else if (s=f) then b2:=mid;
		if t[mid]<p then b2:=b2(mid+1,f,p);
	end;
end;


begin
assign(a,'cautbin.in');
reset(a);
assign(b,'cautbin.out');
rewrite(b);

read(a,n);
for i:=1 to n do
read(a,t[i]);

read(a,m);

for i:=1 to m do
begin
	read(a, tip, p);
	if tip=0 then writeln(b,b0(1,n,p));
	if tip=1 then writeln(b,b1(1,n,p));
	if tip=2 then writeln(b,b2(1,n,p));
end;

close(a);
close(b);
end.