program p1;
var a:array[0..100000] of longint;
    f,g:text;
    i,n,m,u,x,k,poz,s,d:longint;
procedure binn(i_n,s_f:longint);
var mijl , j:longint;
begin
s:=i_n;
d:=S_f;
if i_n<=s_f then begin
        mijl:=(i_n+s_f)div 2;
        if a[mijl]>x then binn(i_n, mijl-1)
                else
                if a[mijl]<x then binn(mijl+1, s_f)
                        else
                        if a[mijl]=x then poz:=mijl;
                  end;
end;

begin
assign(f,'cautbin.in');reset(F);
assign(g,'cautbin.out');rewrite(G);
readln(f,n);
for i:=1to n do read(F,a[i]);
readln(F);
readln(f,m);
k:=1;
for i:=1 to m do
        begin
        readln(f,u,x);
        poz:=0;
        binn(1,n);
        if u=0 then
               if poz =0 then writeln(g,'-1')
                  else       begin
                  while a[poz]=x do inc(poz);
               writeln(g,poz-1);
                end;
        if u=1 then
                if poz=0 then writeln(g,d)
                        else   begin
                      while a[poz]=x do inc(poz);
                writeln(g,poz-1);end;
        if u=2 then
                if poz=0 then writeln(g,s)
                        else    begin
                        while a[poz]=x do dec(poz);
                        writeln(g,poz+1);
                                end;
        end;


close(F);
close(G);
end.