Program Cautbin;
var n,m,i,x : longint;
    A : array[1..100000] of longint;
    op : byte;
    Intrare,Iesire : text;

function poz0(x,lo,hi : longint) : longint;
var mid : longint;
begin
  while lo<>hi do begin
    mid:=lo+(hi-lo) div 2;
    if x<A[mid] then hi:=mid
    else
     if x>A[mid] then lo:=mid+1
     else
      if A[mid+1]=x then lo:=mid+1
      else begin lo:=mid; hi:=mid; end;
  end;
  if A[lo]=x then poz0:=lo else poz0:=-1;
end;

function poz1(x,lo,hi : longint) : longint;
var mid : longint;
begin
  while lo<>hi do begin
    mid:=lo+(hi-lo) div 2;
    if A[mid]>x then hi:=mid
    else
     if A[mid+1]<=x then lo:=mid+1
     else begin lo:=mid; hi:=mid; end;
  end;
  poz1:=lo;
end;

function poz2(x,lo,hi : longint) : longint;
var mid : longint;
begin
  while lo<>hi do begin
    mid:=lo+(hi-lo+1) div 2;
    if A[mid]<x then lo:=mid+1
    else
     if A[mid-1]>=x then hi:=mid-1
     else begin lo:=mid; hi:=mid; end;
  end;
  poz2:=lo;
end;

function poz(op : byte; x : longint) : longint;
begin
  case op of
    0: poz:=poz0(x,1,n);
    1: poz:=poz1(x,1,n);
    2: poz:=poz2(x,1,n);
  end;
end;

begin
  assign(Intrare,'cautbin.in');
  reset(Intrare);
  assign(Iesire,'cautbin.out');
  rewrite(Iesire);
  readln(Intrare,n);
  for i:=1 to n do read(Intrare,A[i]);
  readln(Intrare,m);
  for i:=1 to m do begin
    readln(Intrare,op,x);
    writeln(Iesire,poz(op,x));
  end;
  close(Intrare);
  close(Iesire);
end.