program cautarebinara;
  var n,i,m,op,x:longint;
      a:array[1..100000] of longint;
      bufin,bufout:array[1..100000] of byte;

function c1(l,r,val:longint):longint;
  var m:longint;
  begin
    if l=r then
      begin
        if a[l]=val then c1:=l else c1:=-1;
      end else
      begin
        m:=(l+r) div 2;
        if a[m+1]>val then c1:=c1(l,m,val) else c1:=c1(m+1,r,val);
      end;
  end;

function c2(l,r,val:longint):longint;
  var m:longint;
  begin
    if l=r then c2:=l else
      begin
        m:=(l+r) div 2;
        if a[m+1]>val then c2:=c2(l,m,val) else c2:=c2(m+1,r,val);
      end;
  end;

function c3(l,r,val:longint):longint;
  var m:longint;
  begin
    if l=r then c3:=l else
      begin
        m:=(l+r) div 2;
        if a[m]>=val then c3:=c3(l,m,val) else c3:=c3(m+1,r,val);
      end;
  end;

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

  readln(n);
  for i:=1 to n do read(a[i]);
  readln;
  readln(m);
  for i:=1 to m do
    begin
      readln(op,x);
      if op=0 then writeln(c1(1,n,x)) else
      if op=1 then writeln(c2(1,n,x)) else writeln(c3(1,n,x));

    end;
  close(output);
end.