import java.io.BufferedReader

fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readInt()
    val q = br.readInt()
    val colors = IntArray(n) { br.readInt() - 1 }
    val lefts = IntArray(q)
    val rights = IntArray(q) {
        lefts[it] = br.readInt()
        br.readInt()
    }
    val order = IntArray(q) { it }.sortedWith(Comparator { a, b -> rights[a].compareTo(rights[b]) })
    var idx = 0
    val fenwick = Fenwick(n)
    val answers = IntArray(q)
    val lastOccurrence = IntArray(n)
    for (x in 0 until n) {
        val c = colors[x]
        if (lastOccurrence[c] != 0) {
            fenwick.add(lastOccurrence[c], -1)
        }
        lastOccurrence[c] = x + 1
        fenwick.add(x + 1, 1)
        while (idx < q && rights[order[idx]] == x + 1) {
            answers[order[idx]] = fenwick.get(lefts[order[idx]], rights[order[idx]])
            idx++
        }
    }
    print(answers.joinToString("\n"))
}

private class Fenwick(val size: Int) {
    private val ary = IntArray(size)

    fun add(idx: Int, v: Int) {
        var k = idx
        while (k <= size) {
            ary[k - 1] += v
            k += k and -k
        }
    }

    fun set(idx: Int, v: Int) {
        add(idx, v - get(idx, idx))
    }

    fun get(idx: Int): Int {
        var k = idx
        var r = 0
        while (k > 0) {
            r += ary[k - 1]
            k -= k and -k
        }
        return r
    }

    fun get(a: Int, b: Int): Int {
        return get(b) - get(a - 1)
    }
}

private const val SPACE_INT = ' '.toInt()
private const val ZERO_INT = '0'.toInt()
private const val NL_INT = '\n'.toInt()

private fun BufferedReader.readInt(): Int {
    var ret = read()
    while (ret <= SPACE_INT) {
        ret = read()
    }
    val neg = ret == '-'.toInt()
    if (neg) {
        ret = read()
    }
    ret -= ZERO_INT
    var read = read()
    while (read >= ZERO_INT) {
        ret *= 10
        ret += read - ZERO_INT
        read = read()
    }

    while (read <= SPACE_INT && read != -1 && read != NL_INT) {
        mark(1)
        read = read()
    }
    if (read > SPACE_INT) {
        reset()
    }
    return if (neg) -ret else ret
}