from bisect import bisect_right, bisect_left


def f(r):
    d, m = divmod(r, R)

    p = bisect_left(A, m+1)
    return d * N + p


def g(t):
    res = t // R * N
    t %= R
    return res + bisect_left(A, t+1)


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

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