program cautare_binara;
var
i,n,nr,mi,m,cs,cd,z:longword;
y:byte;
v:array [0..100000] of longword;
f,g:text;

begin
assign(f,'cautbin.in'); reset(f);
assign(g,'cautbin.out'); rewrite(g);

readln(f,n);
for i:=1 to n do read(f,v[i]);
readln(f,m);

for i:=1 to m do
begin
 readln(f,y,nr);

 cs:=1;
 cd:=n;
 mi:=(cs+cd) div 2;

 while (v[mi]<>nr) and (cd-cs>1) do
 begin
  if v[mi]<nr then cs:=mi
  else cd:=mi;

  mi:=(cs+cd) div 2;
 end;

 if y<2 then begin
  while v[mi+1]=nr do inc(mi);

  if v[mi]=nr then writeln(g,mi)
  else begin
   if y=0 then writeln(g,-1);
   if y=1 then
   begin
    if v[mi+1]<nr then inc(mi);
    writeln(g,mi);
   end;
  end;
 end else
 begin
  while v[mi-1]=nr do dec(mi);
  if v[mi-1]>=nr then dec(mi);
  if v[mi]<nr then inc(mi);
  writeln(g,mi);
 end;
end;

close(f);
close(g);
end.