R,N = map(int,input().split())
A =list(map(int,input().split()))
appear = [0]*(R*2)

index = 0
s = 0
for i in range(R*2):
    a = A[index%N]
    if a == i%R:
        s += 1
        index += 1
    appear[i] = s
    
Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    ll = l + (R - (l % R))
    rr = r - (r % R)

    ans = ((rr - ll) // R)*N if ll < rr else 0

    if r < R:
        ln = 0
        if l - 1 > 0:
            ln = appear[l-1]
        rn = appear[r]
        ans += rn - ln
    else:
        ln = 0
        if l - 1 > 0:
            ln = appear[(l-1)%R]
        rn = appear[(R+(r%R))]
        ans += rn -ln
        
    print(ans)