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

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;
	if (s=f) and (t[s]=p) then writeln({b,}s) 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;
	if (s=f) and (t[s]<=p) then writeln({b,}s) 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;
	if (s=f) and (t[s]>=p) then writeln({b,}s) else writeln({b,}'-1');
end;


begin
{assign(a,'cautbin.in');
reset(a);
assign(b,'cautbin.out');
rewrite(b);}
assign(input,'cautbin.in');
reset(input);
assign(output,'cautbin.out');
rewrite(output);
 settextbuf(input,buf);

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.