R, N = map(int, input().split())
A = list(map(int, input().split()))
ex = [False for i in range(R)]
for a in A: ex[a] = True
S = [0 for i in range(R+1)]
for i in range(R):
    S[i] = S[i-1] + ex[i]
for _ in range(int(input())):
    l, r = map(int, input().split())
    lc, rc = l//R, r//R
    if lc == rc:
        print(S[r%R]-S[l%R-1])
    else:
        print(N - S[l%R-1] + S[r%R] + (rc-lc-1) * N)