var a:array[1..100001] of longint;
    n,x,y,o,m,i,b,t:longint;
    f,g:text;
function cb0(b:longint):longint;
var p:longint;
begin
     x:=1; y:=n;    p:=0;
     while x<=y do
     begin
          if p=(x+y)div 2 then inc(p)
                          else p:=(x+y)div 2;
          if (b>a[x])and(b<a[y])and(y-x<=1) then
          begin
               cb0:=-1;
               exit;
          end else
          if b>a[p] then x:=p else
          if b<a[p] then y:=p else
          if b=a[p] then
          begin
               while (b=a[p])and(p<=n) do inc(p);
               cb0:=p-1;
               exit;
          end;
     end;
end;
function cb1(b:longint):longint;
var p:longint;
begin
     x:=1; y:=n;
     while x<=y do
     begin
          p:=(x+y)div 2;
          if (b>=a[x])and(b<=a[y])and(y-x<=1) then
          begin
               cb1:=x;
               exit;
          end else
          if b>a[p] then x:=p else
          if b<a[p] then y:=p else
          if b=a[p] then
          begin
               cb1:=p;
               exit;
          end;
     end;
end;
function cb2(b:longint):longint;
var p,z:longint;
begin
     x:=1; y:=n;
     while x<=y do
     begin
          p:=(x+y)div 2;
          if (b>=a[x])and(b<=a[y])and(y-x<=1) then
          begin
               z:=y;
               break;
          end else
          if b=a[p] then
          begin
               z:=p;
               break;
          end else
          if b>a[p] then x:=p else
          if b<a[p] then y:=p;
     end;
     cb2:=z;
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);
          if t=0 then
          begin
               if b<a[1] then writeln(g,'-1') else
               if b>a[n] then writeln(g,'-1') else writeln(g,cb0(b));
          end;
          if t=1 then
               if b>=a[n] then writeln(g,n)
                          else writeln(g,cb1(b));
          if t=2 then
               if b<=a[1] then writeln(g,'1')
                          else writeln(g,cb2(b));
     end;
     close(g);
end.