R, N = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
Q = int(input())

import bisect
def f(x):
    res = 0
    res = x // R * N
    m = x % R
    res1 = bisect.bisect_right(A, m)
    return res + res1

for _ in range(Q):
    l, r = map(int, input().split())
    ans = f(r) - f(l-1)
    print(ans)