R, N = map(int, input().split())
A = list(map(int, input().split()))
appear = [0] * R  # R 個の要素で初期化

# `appear` 配列を計算
index = 0
s = 0
for i in range(R):
    a = A[index % N]
    if a == i:
        s += 1
        index += 1
    appear[i] = s

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())

    ll = ((l + R - 1) // R) * R
    rr = (r // R) * R


    ans = 0
    if ll <= rr:
        ans += ((rr - ll) // R) * N
    
    if l % R != 0:
        ln = 0
        if l % R > 0:
            ln = appear[(l - 1) % R]
        rn = appear[r % R] if r < R else appear[R - 1]
        ans += rn - ln


    if r % R != 0 and r >= R:
        ans += appear[r % R]
    
    print(ans)