var v:array[1..100000] of longint;
n,i,m,nr,x,a,b,mid:longint;
f,g:text;
bufin:array[0..100000] of byte;
begin
assign(f,'cautbin.in');
assign(g,'cautbin.out');
reset(f);rewrite(g);
settextbuf(f,bufin);
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,nr,x);
    a:=1;b:=n;
    case nr of
         0:begin
           while a<=b do
                 begin
                 mid:=(a+b) div 2;
                 if v[mid]>x then
                    b:=mid-1
                 else
                     a:=mid+1;
                 end;
           if v[b]=x then
              writeln(g,b)
           else
               writeln(g,-1);
           end;
         1:begin
           while a<=b do
                 begin
                 mid:=(a+b) div 2;
                 if v[mid]>x then
                    b:=mid-1
                 else
                     a:=mid+1;
                 end;
           writeln(g,b);
           end;
         2:begin
           while a<=b do
                 begin
                 mid:=(a+b) div 2;
                 if v[mid]<x then
                    a:=mid+1
                 else
                     b:=mid-1;
                 end;
           writeln(g,a);
           end;
         end;
    end;
close(f);close(g);
end.