fun main() {
    val data = readln().split(" ").map { it.toInt() }
    val ro = data[0]
    val n = data[1]
    val a = readln().split(" ").map { it.toInt() }.sorted()


    val q = readln().toInt()
    for (j in 0..q-1 ) {
        val data1 = readln().split(" ").map { it.toInt() }
        val ll = data1[0]
        val rr = data1[1]


        val ln = ll / ro
        var la = ll % ro
        val rn = rr / ro
        val ra = rr % ro
        var rs = 0
        var count :Int

        if (rn-ln==0){
            count=0

        }else
        count = n * (rn - ln -1)





        for (i in 0..n -1) {
            val a = a[i]

            if ((rn-ln== 0) && (la <= a && a <= ra )){

                count = count + 1


            }else
            if ((la <= a && a <= ro ) || (rs <= a && a <= ra )){
                count = count + 1
                la = a
                rs = a

            }

        }

        println(count)
    }

}