R, N = map(int, input().split())
A = list(map(int, input().split()))
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]

ok_list_origin = [True if r in A else False for r in range(R)]


for l, r in lr:
    ok_list = ok_list_origin*(r//R+1)
    print(ok_list[l:r+1].count(True))