var     a:array[0..100000] of int64;
        x:int64;
        c,poz,n,m,i:longint;
        buf:array[1..1000000] of longint;
        f1,f2:text;

function caut0(p:int64):longint;
var     l,r,mij:longint;
begin
  l:=1;
  r:=n;
  while l<>r do
    begin
      mij:=(l+r) div 2;
      if a[mij]<=p then l:=mij+1 else r:=mij;
    end;
  caut0:=l-1;
end;

function caut1(p:int64):longint;
var     l,r,mij:longint;
begin
  l:=1;
  r:=n;
  while l<>r do
    begin
      mij:=(l+r) div 2;
      if a[mij]<=p then l:=mij+1 else r:=mij;
    end;
  caut1:=l-1;
end;

function caut2(p:int64):longint;
var     l,r,mij:longint;
begin
  l:=1;
  r:=n;
  while l<>r do
    begin
      mij:=(l+r) div 2;
      if a[mij]>=p then r:=mij else l:=mij+1;
    end;
  caut2:=l;
end;

begin
  assign(f1,'cautbin.in');
  assign(f2,'cautbin.out');
  reset(f1);
  rewrite(f2);
  settextbuf(f1,buf);
  readln(f1,n);
  for i:=1 to n do
    read(f1,a[i]);
  readln(f1,m);
  for i:=1 to m do
    begin
      read(f1,c,x);
      if c=0 then
        begin
          poz:=caut0(x);
          if a[poz]=x then writeln(f2,poz) else writeln(f2,-1);
        end;
      if c=1 then
        begin
          poz:=caut1(x);
          writeln(f2,poz);
        end;
      if c=2 then
        begin
          poz:=caut2(x);
          writeln(f2,poz);
        end;
    end;
  close(f2);
end.