from bisect import bisect_left, bisect

R,N=map(int,input().split())

A=list(map(int,input().split()))
ko=len(A)
Q=int(input())

for tests in range(Q):
    l,r=map(int,input().split())
    ANS=(r-l)//R*ko
    l=l%R
    r=r%R

    if l<=r:
        ANS+=bisect(A,r)-bisect_left(A,l)
    else:
        ANS+=ko-bisect_left(A,l)
        ANS+=bisect(A,r)

    print(ANS)