I,R=input,range
J=lambda:map(int,I().split())
P,N=J()
H=[0]*(P+1)
for a in J():H[a+1]+=1
for i in R(1,P):H[i+1]+=H[i]
for _ in R(int(I())):l,r=J();d=l-l%P;r-=d;print(r//P*H[P]-H[l-d]+H[r%P+1])