var n,x,q,m,y:int64; i,j:longint;
ook:boolean;
v:array[1..10000]of int64;
w:array[1..10000]of int64;
f,g:text;
begin
assign(f,'cautbin.in');reset(f);
assign(g,'cautbin.out');rewrite(g);
readln(f,n);
for i:=1 to n do begin
read(f,v[i]);w[v[i]]:=w[v[i]]+1;end; readln(f);
readln(f,m);
for i:=1 to m do begin
readln(f,y,x);
for j:=1 to n do begin
 if (v[j]=x)and(j=n)then q:=j;
 if v[j]=x then  ook:=true
 else if (v[j]>x)and(ook=true) then begin q:=j-1;break;end
 else if (v[j]>x)and(ook=false) then begin q:=j;break;end;end;
 if ook=true then begin
 if y=0 then writeln(g,q) else
 if y=1 then writeln(g,q) else
 if y=2 then writeln(g,q-w[x]+1);end else
 if y=0 then writeln(g,'-1') else
 if y=1 then writeln(g,q) else
 if y=2 then writeln(g,q-1);end;
close(f);close(g);end.