var a,b,c,d,i,o,start,endl,mid,last:longint;
este:boolean;
fin,fout:textfile;
type vector = array[1..100005] of longint;
var x:vector;
begin
  assign(fin,'cautbin.in');
  reset(fin);
  assign(fout,'cautbin.out');
  rewrite(fout);
  start:=1;
  read(fin,a);
  endl:=a;
  for i:=1 to a do begin
    read(fin,x[i]);
    end;
  read(fin,b);
  for i:=1 to b do begin
    read(fin,c,d);
    last:=0;
    mid:=0;
    start:=1;
    endl:=a;
    if c=0 then begin
      while start<= endl do begin
        mid:=start+((endl-start)div 2);
        //writeln('mid=',mid,' start=',start,' end=',endl,' last=',last);
        if x[mid]=d then begin
          este:=true;
          last:=mid;
          start:=mid+1;
          end
        else if x[mid]<d then begin
          start:=mid+1;
          end
        else begin
          endl:=mid-1;
          end;
        end;
      if last=0 then writeln(fout,'-1')
      else writeln(fout,last);
      end;
    if c=1 then begin  
      while start<= endl do begin
        mid:=start+((endl-start)div 2);
        //writeln('mid=',mid,' start=',start,' end=',endl,' last=',last);
        if x[mid]<=d then begin
          este:=true;
          last:=mid;
          start:=mid+1;
          end
        else if x[mid]<d then begin
          start:=mid+1;
          end
        else begin
          endl:=mid-1;
          end;
        end;
      if last=0 then writeln(fout,'-1')
      else writeln(fout,last);
      end;    
    if c=2 then begin  
      while start<= endl do begin
        mid:=start+((endl-start)div 2);
        //writeln('mid=',mid,' start=',start,' end=',endl,' last=',last);
        if x[mid]>=d then begin
          este:=true;
          last:=mid;
          endl:=mid-1;
          end
        else if x[mid]<d then begin
          start:=mid+1;
          end
        else begin
          endl:=mid-1;
          end;
        end;
      if last=0 then writeln(fout,'-1')
      else writeln(fout,last);
      end;      
  end;
  close(fin);
  close(fout);
end.