import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val jin = BufferedReader(InputStreamReader(System.`in`))
    val (n, q) = jin.readLine().split(" ").map { it.toInt() }
    val next = IntArray(n + 1)
    val last = IntArray(n + 1)
    val colors = listOf(0) + jin.readLine().split(" ").map { it.toInt() }
    val bit = BinaryIndexTree(1, n)
    for (j in 1..n) {
        if (last[colors[j]] == 0) {
            bit.update(j, 1)
        }
        next[last[colors[j]]] = j
        last[colors[j]] = j
    }
    val queries = Array(q) {
        val (l, r) = jin.readLine().split(" ").map { it.toInt() }
        Query(it, l, r)
    }
    queries.sortBy { it.from }
    val answer = IntArray(q)
    var from = 1
    for (query in queries) {
        while (from < query.from) {
            bit.update(from, -1)
            if (next[from] != 0) {
                bit.update(next[from], 1)
            }
            from++
        }
        answer[query.ix] = bit.query(query.to)
    }
    println(answer.joinToString("\n"))
}

data class Query(val ix: Int, val from: Int, val to: Int)

class BinaryIndexTree(val treeFrom: Int, treeTo: Int) {
    val value = IntArray(treeTo - treeFrom + 2)

    fun update(index: Int, delta: Int) {
        var i = index + 1 - treeFrom
        while (i < value.size) {
            value[i] += delta
            i += i and -i
        }
    }

    fun query(to: Int): Int {
        var res = 0
        var i = to + 1 - treeFrom
        while (i > 0) {
            res += value[i]
            i -= i and -i
        }
        return res
    }
}