var a:array[1..100000] of longint;
    n,m,i,val,p:longint;

    f,g:text;

function bin0(st:longint;dr:longint;k:longint):longint;
begin
        while st<=dr do
        begin
                m := (st+dr) div 2;
                if a[m]<=k then st := m+1
                           else dr := m-1;
        end;

        m:=(st+dr) div 2;

        if a[m]>k then dec(m);
        if a[m]=k then bin0 := m else bin0:=-1;
end;

function bin1(st:longint;dr:longint;k:longint):longint;
begin
        while st<dr do
        begin
                m := (st+dr) div 2;
                if a[m]<=k then st := m+1
                           else dr := m;
        end;

        m:=(st+dr) div 2;

        if a[m]>k then dec(m);
        bin1 := m;
end;

function bin2(st:longint;dr:longint;k:longint):longint;
begin
        while st<dr do
        begin
                m := (st+dr) div 2;
                if a[m]<k then st := m+1
                          else dr := m;
        end;

        m:=(st+dr) div 2;

        if a[m]<k then inc(m);
        bin2:=m;
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,m);

for i:=1 to m do
begin
        readln(f,p,val);
        if p=0 then writeln(g,bin0(1,n,val));
        if p=1 then writeln(g,bin1(1,n,val));
        if p=2 then writeln(g,bin2(1,n,val));
end;

close(g);
end.