Program P1;
  var fi,fo:text;
      n,i,m,dr,st,a,mid,x:integer;
      s:array[1..100000] of integer;
begin
    assign(fi,'cautbin.in');
    assign(fo,'cautbin.out');
    reset(fi);
    rewrite(fo);
    readln(fi,n);
    For i:=1 to n do
                  read(fi,s[i]);
    readln;
    readln(fi,m);
    While not eof do readln(fi,a,x);
    dr:=n;
    st:=1;
    If a=0 then begin
                 while st<=dr do begin
                                     mid:=(st+dr) div 2;
                                     If s[mid]<=x then st:=mid+1
                                                  else dr:=mid-1;
                                 end;
                                 mid:=(st+dr) div 2;
                                 If s[mid]=x then write(fo,mid)
                                             else If s[mid-1]=x then
                                                                   write(fo,mid-1)
                                                              else write(fo,-1);
                end
           else If a=1 then begin
                               while st<dr do begin
                                     mid:=(st+dr) div 2;
                                     If s[mid]<=x then st:=mid+1
                                                  else dr:=mid;
                                 end;
                                 mid:=(st+dr) div 2;
                                If s[mid]>x then
                                                 write(fo,mid-1)
                                            else write(fo,mid);
                            end
                       else If a=2 then begin
                                             while st<dr do begin
                                                             mid:=(st+dr) div 2;
                                                             If s[mid]<x then st:=mid+1
                                                                         else dr:=mid;
                                                             end;
                                                             mid:=(st+dr) div 2;
                                                             If s[mid]<x then
                                                                              write(fo,mid+1)
                                                                         else write(fo,mid);
                                         end;
           close(fi);
           close(fo);
    end.