program binarsearch;
    type vector1=array[0..100001] of longint;
         buf=array[0..1 shl 17] of char;
    var t:vector1; ff1,ff2:buf;
        n,i,tip,x,m:longint;
        f1,f2:text;
function cauta1(st,dr,x:longint):longint;
    var m,sol:longint;
    begin
        sol:=-1;
        while st<=dr do begin
                            m:=(st+dr) div 2;
                            if t[m]=x then sol:=m;
                            if t[m]>x then dr:=m-1 else st:=m+1;
                        end;
        cauta1:=sol;
        end;
function cauta2(st,dr,x:longint):longint;
    var m,sol:longint;
    begin
        sol:=0;
        while (st<=dr) do begin
                              m:=(st+dr) div 2;
                              if t[m]<=x then begin
                                                  sol:=m;
                                                  st:=m+1;
                                              end else dr:=m-1;
                          end;
        cauta2:=sol;
    end;
function cauta3(st,dr,x:longint):longint;
    var m,sol:longint;
    begin
        sol:=0;
        while (st<=dr) do begin
                              m:=(st+dr) div 2;
                              if t[m]>=x then begin
                                                  sol:=m;
                                                  dr:=m-1;
                                              end else st:=m+1;
                          end;
        cauta3:=sol;
    end;
begin
    assign (f1,'cautbin.in');
    assign (f2,'cautbin.out');
    reset (f1);
    rewrite (f2);
    settextbuf(f1,ff1);
    settextbuf(f2,ff2);
    readln (f1,n);
    for i:=1 to n do read (f1,t[i]);
    readln (f1,m);
    for i:=1 to m do begin
                         readln (f1,tip,x);
                         if tip=0 then writeln (f2,cauta1(1,n,x)) else
                         if tip=1 then writeln (f2,cauta2(1,n,x)) else
                         writeln (f2,cauta3(1,n,x));
                     end;
    close (f1);
    close (f2);
end.