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

function b0(s,f: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) else if
		{if (t[mid]=p) and }(s=f) then b0:=mid;
		if t[mid]<p then b0:=b0(mid+1,f);
		if t[mid]>p then b0:=b0(s,mid-1);
	end;
end;

function b1(s,f: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) else if
		{if (t[mid]<=p) and }(s=f) then b1:=mid;
		if t[mid]>p then b1:=b1(s,mid-1);
	end;
end;

function b2(s,f:longint):longint;
var mid:longint;
begin
	if s>f then b2:=-1 else
	begin
		mid:=((s+f) div 2){ + ((s+f) mod 2)};
		if (t[mid]>=p) and (s<>f) then b2:=b2(s,mid) else if
		{if (t[mid]>=p) and} (s=f) then b2:=mid;
		if t[mid]<p then b2:=b2(mid+1,f);
	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);
	case tip of
	0:writeln(b,b0(1,n));
	1:writeln(b,b1(1,n));
	2:writeln(b,b2(1,n));
	end;
end;

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