fun main() {
    val (round, n) = readln().split(" ").map { it.toInt() }
    val a = readln().split(" ").map { it.toInt() }.toMutableList()
    val q = readln().toInt()

    for(i in 0..<n) {
        a.add(a[i] + round)
    }
    val s = a.toSet()

    for(i in 0..<q) {
        var (l, r) = readln().split(" ").map { it.toInt() }
        var cnt = (r - l) / round * n

        // 0 <= l < R
        // l < r < 2R
        l %= round
        r %= round
        if(r < l) r += round

        var li = a.binarySearch(l)
        if(li < 0) li += 2*n
        else cnt += 1

        var ri = a.binarySearch(r)
        if(ri < 0) ri += 2*n

        cnt += ri - li
        println(cnt)
    }
}