type tablou=array [1..100000]of int64;
var t:tablou;
    k,m,n,st,fn,mid,p,q:int64;
    i,j:longint;
    f,g:text;
begin
assign(f,'cautbin.in');
assign(g,'cautbin.out');
reset(f);
rewrite(g);
readln(f,n);
for i:=1 to n do
  read(f,t[i]);
readln(f,m);
for i:=1 to m do
  begin
    readln(f,p,q);
    st:=1;
    fn:=n;
    if p=0 then begin
                  while st<=fn do
                    begin
                     mid :=(st+fn)div 2;
                     if t[mid]<=q then st:=mid+1
                      else fn:=mid-1;
                    end;
                  mid:=(st+fn)div 2;
                  if t[mid]>q then mid:=mid-1;
                  if t[mid]<>q then writeln(g,-1)
                     else writeln(g,mid);
                end
   else if p=1 then begin
                   while st<fn do
                     begin
                       mid:=(st+fn) div 2;
                       if t[mid]<=q then st:=mid+1
                         else fn:=mid;
                     end;
                     mid:=(st+fn) div 2;
                     if t[mid]>q then mid:=mid-1;
                     writeln(g,mid);
                   end
   else begin
              while st<fn do
                begin
                   mid:=(st+fn) div 2;
                   if t[mid]>=q then fn:=mid
                    else st:=mid+1;
                end;
              mid:=(st+fn) div 2;
              if (t[mid]<q) then mid:=mid+1;
              writeln(g,mid);
              end;
  end;
close(f);
close(g);
end.