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


function cod(x:longint):longint;
label   1;
var     i,j:longint;
begin
  i:=1;
  j:=0;
1: while (a[j+2*i]<x)and(j+i*2<=n) do i:=i*2;
  if a[j+i]<x then begin j:=j+i; i:=1; goto 1; end;
  cod:=i+j;
end;

{function cod1(x:longint):longint;
var     i,j:longint;
begin
  if a[n]<x then cod1:=n
  else
    begin
      i:=1;
      j:=0;
      while a[j+i*2]<x do
        begin
          i:=i*2;
          if a[j+i]<>x then if a[j+i*2]>x then begin j:=j+i; i:=1; end;
          if i*2>n then break;
        end;
      cod1:=j+2*i-1;
    end;
end;

function cod2(x:longint):longint;
var     i,j:longint;
begin
  if a[1]>x then cod2:=1
  else
    begin
      i:=1;
      j:=0;
      while a[j+i]<x do
        begin
          i:=i*2;
          if a[j+i]<>x then if a[j+i*2]>x then begin j:=j+i; i:=1; end;
          if i*2>n then break;
        end;
      if a[j+2*i]=x then cod2:=j+2*i+1
      else cod2:=j+2*i;
    end;
end;
}
begin
  assign(f1,'cautbin.in');
  assign(f2,'cautbin.out');
  reset(f1);
  rewrite(f2);
  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 a[n]>=x then poz:=cod(x);

      if c=0 then begin if ((a[n]<x)or(a[poz]>x)) then writeln(f2,-1) else begin
        while a[poz+1]=x do inc(poz); writeln(f2,poz); end; end else
      if c=1 then if a[n]<x then writeln(f2,n) else if a[poz]=x then begin
        while a[poz+1]=x do inc(poz); writeln(f2,poz) end
        else writeln(f2,poz-1) else
      if c=2 then writeln(f2,poz);
    end;
  close(f2);
end.