var v:array[1..100000] of longint; {00}
n,m,i,k,mij,r,st,dr,x,c:longint;
f,g:text; ok:boolean;
begin
assign(f,'cautbin.in');reset(f);
assign(g,'cautbin.out');rewrite(g);
read(f,n);
for i:=1 to n do read(f,v[i]);
read(f,m);
for k:=1 to m do
    begin
    read(f,c,x);
    if c=0 then
           begin
           st:=1; dr:=n; ok:=true; r:=-1;
              while (st<=dr) and ok do
                    begin
                    mij:=st+(dr-st) div 2;
                    if x>v[mij] then st:=mij+1
                       else if x<v[mij] then dr:=mij-1
                            else
                                begin
                                r:=mij;
                                ok:=false;
                                break;
                                end;
                    end;
           writeln(g,r);
           end
      else if c=1 then
              begin
              st:=1; dr:=n; r:=0;
              while (st<=dr) do
                    begin
                    mij:=st+(dr-st) div 2;
                    if x>=v[mij] then   begin
                                        st:=mij+1;
                                        r:=mij;
                                        end
                       else dr:=mij-1;
                    end;
              writeln(g,r);
              end
         else
              begin
              st:=1; dr:=n; r:=0;
              while (st<=dr) do
                    begin
                    mij:=st+(dr-st) div 2;
                    if x<=v[mij] then   begin
                                        dr:=mij-1;
                                        r:=mij;
                                        end
                       else st:=mij+1;
                    end;
              writeln(g,r);
              end;
    end;
close(f);
close(g);
end.