Program cautbin;
 var a:array [1..100001] of longint;
    i,j,n,nr,x,m,pos,st,dr:longint;
    fi,fo:text;
procedure cauta(i,sf:integer);
 var mid,j:longint;
begin
st:=i; dr:=sf;
if i<=sf then begin
 mid:=(i+sf) div 2;
 if a[mid]>x then cauta(i,mid-1)
 else if a[mid]<x then cauta(mid+1,sf);
 if a[mid]=x then pos:=mid;
                end;
end;
begin
 assign(fi,'cautbin.in');
  assign(fo,'cautbin.out');
 reset(fi);
  rewrite(fo);
 readln(fi,n);
 for i:=1 to n do read(fi,a[i]);
 readln(fi);
 readln(fi,m);
 for i:=1 to m do begin
                   readln(fi,nr,x);
                   pos:=0;
                    cauta(1,n);
                   if nr=0 then
                    if pos=0 then writeln(fo,'-1')
                     else begin
                           while a[pos]=x do inc(pos);
                           writeln(fo,pos-1);
                           end;
                   if nr=1 then
                    if pos=0 then begin
                                    if a[dr]<x then begin
                                                     while a[dr]<x do inc(dr);
                                                     writeln(fo,dr-1);
                                                     end
                                    else begin
                                         while a[dr]>x do dec(dr);
                                         writeln(fo,dr+1);
                                         end;
                                    end
                     else begin
                           while a[pos]=x do inc(pos);
                           writeln(fo,pos-1);
                           end;
                   if nr=2 then
                   if pos=0 then begin
                                  if a[st]<x then begin
                                     while a[st]<x do inc(st);
                                      writeln(fo,st);
                                                  end
                                  else begin
                                         while a[st]>x do dec(st);
                                         writeln(fo,st+1);
                                         end;
                                  end
                    else  begin
                           while a[pos]=x do dec(pos);
                           writeln(fo,pos+1);
                           end;
                    end;
 close(fo);
end.