var a:array[1..100000] of longint;
    n,m,i,b,t:longint;
    f,g:text;
function cb(t,b,x,y:longint):longint;
var p:longint;
begin
     if y-x>1 then
     begin
          p:=(x+y)div 2;
          if b>a[p] then cb:=cb(t,b,p,y)
                    else cb:=cb(t,b,x,p);
     end
              else
     begin
          if t=0 then
          begin
               while (a[x]<=b)and(x<=n) do inc(x);
               dec(x);
               if a[x]=b then cb:=x
                         else cb:=-1;
          end;
          if t=1 then cb:=x;
          if t=2 then cb:=y;
     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,a[i]);
     readln(f,m);
     for i:=1 to m do
     begin
          readln(f,t,b);
          writeln(g,cb(t,b,1,n));

     end;
     close(g);
end.