var v:array[1..100000] of longint;
        nr,n,m,i:longint;
       k:byte;
       f,g:text;

    function binar(a,b:longint):longint;
    var m:longint; ok:boolean;
    begin
      ok:=false;
     while a<b do
       begin
        m:=(a+b) div 2;
         if nr=v[m] then begin while nr=v[m] do inc(m); dec(m); ok:=true; break; end
         else
           if nr<v[m] then b:=m-1
                      else a:=m+1;
       end;
     if not ok then
       if nr<v[a] then m:=a-1
                  else m:=a;
     if k=0 then begin
       if v[m]=nr then binar:=m
                    else binar:=-1;end
       else if k=1 then binar:=m
       else begin while v[m]=nr do dec(m); binar:=m+1; end;
     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,v[i]);  
     readln(f,m);  
     for i:=1 to m do  
      begin  
        readln(f,k,nr);  
         writeln(g,binar(1,n));  
       end;  
     close(f);  
     close(g);  
  end.