program p1;
var a:Array[0..1000000] of int64;
    f,g:text;
    i,n,m,u,k,j,mid:longint;
    x:int64;
    p:boolean;
procedure cauta(i,j:longint);
begin
if (i<=j) then begin
                mid:=(i+j) div 2;
                if x=a[mid] then p:=true;
                if x>a[mid] then cauta(mid+1,j);
                if x<a[mid] then cauta(i+1,mid);
            end;
end;
begin
assign(f,'cautbin.in');reset(F);
assign(g,'cautbin.out');rewrite(G);
readln(f,n);
for i:=1 to n do read(f,a[i]);
readln(F);
readln(f,k);
for i:=1 to k do
        begin
        readln(f,u,x);
        p:=false;
        cauta(1,n);
        if u=0 then  begin
                if p=false then writeln(g,'-1');
                if p then  begin
                        while a[mid]=x do inc(mid);
                        writeln(g,mid-1);
                                end;
                        end;
        if u=1 then  begin
                while a[mid]=x do inc(mid);
                writeln(g,mid-1);
                      end;
        if u=2 then begin
                while a[mid]=x do dec(mid);
                writeln(G,mid+1);
                        end;
        end;
close(G);
end.