Type vector=array[1..100000] of longint;
var f,g:text;
    a:vector;
    n,i,m,a1,b,p:longint;

function cautbinar(var x:vector;y:longint):longint;
var st,dr,m:longint;
    ok:boolean;
Begin
st:=1;
dr:=n;
ok:=false;
While (st<=dr) and (not ok) do
 Begin
  m:=(st+dr) div 2;
  If x[m]=y then Begin
                  ok:=true;
                  cautbinar:=m;
                 end
            else If x[m]>y then dr:=m-1
                           else st:=m+1;
 end;
If not ok then cautbinar:=-1;
end;

function cautbinar1(var x:vector;y:longint):longint;
var st,dr,m:longint;
    ok:boolean;
Begin
st:=1;
dr:=n;
ok:=false;
While (st<=dr) and (not ok) do
 Begin
  m:=(st+dr) div 2;
  If x[m]<=y then Begin
                  ok:=true;
                  cautbinar1:=m;
                 end
            else If x[m]>y then dr:=m-1
                           else st:=m+1;
 end;
If not ok then cautbinar1:=-1;
end;

function cautbinar2(var x:vector;y:longint):longint;
var st,dr,m:longint;
    ok:boolean;
Begin
st:=1;
dr:=n;
ok:=false;
While (st<=dr) and (not ok) do
 Begin
  m:=(st+dr) div 2;
  If x[m]>=y then Begin
                  ok:=true;
                  cautbinar2:=m;
                 end
            else If x[m]>y then dr:=m-1
                           else st:=m+1;
 end;
If not ok then cautbinar2:=-1;
end;



Begin
Assign(f,'cautbin.in');Reset(f);
Assign(g,'cautbin.out');Rewrite(g);
Readln(f,n);
For i:=1 to n do Read(f,a[i]);
Readln(f,m);
For i:=1 to m do
 Begin
  Readln(f,a1,b);
  If a1=0 then Begin
               p:=cautbinar(a,b);
               If p=-1 then Writeln(g,p)
                       else Begin
                             While (p<n) and (a[p+1]=b) do p:=p+1;
                             Writeln(g,p);
                            end;
              end;
  If a1=1 then Begin
                p:=cautbinar1(a,b);
                Writeln(g,p);
               end;
  If a1=2 then Begin
                p:=cautbinar2(a,b);
                Writeln(g,p);
               end;
 end;
Close(f);
Close(g);
end.