const maxn=100001;
type vector=array[0..maxn]of longint;
var n,i,m,x:longint;
    v:vector;
    tip:byte;
    p,q,r,s:longint;

procedure caut;
begin
p:=1;
q:=n;
repeat
r:=(p+q)div 2;
s:=v[r];
if s=x then exit
       else if x<s then q:=r-1
                   else p:=r+1;
until p>q;
end;


function caut0:longint;
begin
p:=1;
q:=n;
repeat
r:=(p+q)div 2;
s:=v[r];
if(s=x)and(v[r+1]<>x)then begin
                          caut0:=r;
                          exit;
                          end
                     else if x<s then q:=r-1
                                 else p:=r+1;
until p>q;
caut0:=-1;
end;

function caut1:longint;
begin
if x<>v[r+1]then begin
                 caut1:=r;
                 exit;
                 end
            else if x<s then q:=r-1
                        else p:=r+1;
while p<=q do
  begin
  r:=(p+q)div 2;
  s:=v[r];
  if(s=x)and(x<>v[r+1])then begin
                            caut1:=r;
                            exit;
                            end
                       else if x<s then q:=r-1
                                   else p:=r+1;
  end;
caut1:=-1;
end;

function caut2:longint;
begin
if x<>v[r-1]then begin
                 caut2:=r;
                 exit;
                 end
            else if x<=s then q:=r-1
                         else p:=r+1;
while p<=q do
  begin
  r:=(p+q)div 2;
  s:=v[r];
  if(s=x)and(x<>v[r-1])then begin
                            caut2:=r;
                            exit;
                            end
                       else if x<=s then q:=r-1
                                    else p:=r+1;
  end;
caut2:=-1;
end;

begin
assign(input,'cautbin.in');
reset(input);
assign(output,'cautbin.out');
rewrite(output);
read(n);
v[0]:=-1;
for i:=1 to n do read(v[i]);
v[n+1]:=maxlongint;
read(m);
for i:=1 to m do
  begin
  read(tip,x);
  case tip of
    0:if x=maxlongint then writeln(n)
                      else writeln(caut0);
    1:if x=maxlongint then writeln(n)
                      else
        begin
        caut;
        if s=x then writeln(caut1)
               else
          begin
          if s>x then while v[r]>x do dec(r)
                 else while not((v[r]<=x)and(x<v[r+1]))do inc(r);
          writeln(r);
          end;
        end;
    2:begin
      caut;
      if s=x then writeln(caut2)
             else
        begin
        if s>x then while not((v[r]>=x)and(x>v[r-1])) do dec(r)
               else while v[r]<x do inc(r);
        writeln(r);
        end;
      end;
    end;
  end;
close(output);
close(input);
end.