var a:array[1..100000,1..2]of longint;
v:array[1..100000]of longint;
max,k,m:integer;i,n:longint;
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 read(f,v[i]);readln(f);
read(f,m);
for i:=1 to m do begin
for k:=1 to 2 do
read(f,a[i,k]);readln(f);end;
for i:=1 to m do begin max:=-1;
if a[i,1]=0 then
if a[i,2]<v[n div 2] then begin
for k:=1 to n div 2 do
if v[k]=a[i,2] then  max:=k;writeln(g, max);end else begin
for k:=(n div 2) to n do
if v[k]=a[i,2] then max:=k;writeln(g,max);end else begin
if a[i,1]=1 then
if v[n div 2]>a[i,2] then begin
for k:=1 to n div 2 do
if v[k]<=a[i,2] then max:=k;writeln(g,max);end else begin
for k:=(n div 2) to n do
if v[k]<=a[i,2] then max:=k;writeln(g,max);end;
if a[i,1]=2 then
if v[n div 2]>=a[i,2]then begin
for k:=1 to n div 2 do
if v[k]>=a[i,2] then begin writeln(g,k);break;end;end else
for k:=(n div 2)+1 to n do
if v[k]>=a[i,2] then begin writeln(g,k);break;end;end;end;
close(g);close(f);end.