{$s-}
program caut;
var f,g:text;
    v:array[1..100000]of longint;
    n,m,i,elem:longint;
    int:byte;
function zero(elem:longint):longint;
var a,b,c:longint;
    ok:boolean;
begin
ok:=false;
a:=1;b:=n;
while a<>b do begin
      c:=(a+b) div 2;
      if elem=v[c] then begin
                        ok:=true;
                        break;
                        end
      else
      if v[c]<elem then a:=c+1
                   else b:=c;
end;
if ok then begin
      while v[c]=elem do inc(c);
      dec(c);
      end;
if (int=0)and(ok) then zero:=c
                  else if int=0 then zero:=-1;
if (int=2)and(ok)then zero:=c+1
                 else if int=2 then zero:=c;
if (int=1)and(ok) then begin
                       while v[c]=elem do dec(c);
                       zero:=c;
                       end
                       else if int=1 then zero:=c;
end;
begin
assign(f,'cautbin.in');
assign(g,'cautbin.out');
reset(f);rewrite(g);
readln(f,n);
for i:=1 to n do read(f,v[i]);
readln(f,m);
for i:=1 to m do begin
    readln(f,int,elem);
    writeln(g,zero(elem));
end;
close(f);close(g);
end.