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

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

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

procedure b2(s,f:longint);
var mid:longint;
begin
	while s<f do
	begin
		mid:=(s+f) div 2;
		if (t[mid]>=p) then f:=mid else
		if t[mid]<p then s:=mid+1;
	end;
	mid:=(s+f) div 2;
	if (s=f) and (t[mid]>=p) then writeln(b,mid) else writeln(b,'-1');
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 b0(1,n);
	if tip=1 then b1(1,n);
	if tip=2 then b2(1,n);
end;

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