type tab=array[1..100001] of longint;
var 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(s) else writeln('-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(s) else writeln('-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(s) else writeln('-1');
end;


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

read(n);

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

read(m);

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

end.