fun main() = abc174f()

@OptIn(ExperimentalStdlibApi::class)
fun abc174f() = IO_abc174f().exec {
    data class Query(val index: Int, val left: Int, val right: Int)

    val (n, q) = readIntList(2)
    val balls = readIntList(n).map { it - 1 }.toIntArray()
    val queries = List(q) { Query(it, readInt() - 1, readInt() - 1) }

    // [color] = last appeared index
    val beforeSameColorAppearedIndicesByColor = IntArray(n) { -1 }
    // [index] = before same color appeared index
    val beforeSameColorAppearedIndices = IntArray(n) { -1 }
    for (i in balls.indices) {
        val color = balls[i]
        val beforeSameColorAppearedIndex = beforeSameColorAppearedIndicesByColor[color]
        if (beforeSameColorAppearedIndex != -1) beforeSameColorAppearedIndices[i] = beforeSameColorAppearedIndex
        beforeSameColorAppearedIndicesByColor[color] = i
    }

    // count same color appeared
    val segmentTree = SegmentTree(LongArray(n), 0L, Long::plus)
    val rightIndexToQueries = queries.groupBy { it.right }

    val answers = LongArray(q)

    for (right in 0 until n) {
        val beforeSameColorAppearedIndex = beforeSameColorAppearedIndices[right]
        if (beforeSameColorAppearedIndex != -1) segmentTree[beforeSameColorAppearedIndex]++
        for ((index, left, _) in rightIndexToQueries[right].orEmpty()) {
            answers[index] = (right - left + 1) - segmentTree[left..right]
        }
    }

    val answer = answers.joinToString(System.lineSeparator())

    println(answer)
}

private class SegmentTree(init: LongArray, val identityElement: Long, val monad: (Long, Long) -> Long) {
    val indices: Int
    val nodes: LongArray

    init {
        var indices = 1
        while (indices < init.size) indices = indices shl 1
        val nodes = LongArray(2 * indices - 1) { identityElement }
        for (i in init.indices) nodes[i + indices - 1] = init[i]
        for (i in indices - 2 downTo 0) nodes[i] = monad(nodes[2 * i + 1], nodes[2 * i + 2])
        this.indices = indices
        this.nodes = nodes
    }

    operator fun set(x: Int, value: Long) {
        var index = x + indices - 1
        nodes[index] = value
        while (index > 0) {
            index = (index - 1) / 2
            nodes[index] = monad(nodes[2 * index + 1], nodes[2 * index + 2])
        }
    }

    operator fun get(range: IntRange) = get(range.first, range.last + 1)

    operator fun get(index: Int) = get(index, index + 1)

    fun get(a: Int, b: Int, k: Int = 0, l: Int = 0, r: Int = indices): Long {
        if (r <= a || b <= l) return identityElement
        if (a <= l && r <= b) return nodes[k]
        return monad(
            get(a, b, 2 * k + 1, l, (l + r) / 2),
            get(a, b, 2 * k + 2, (l + r) / 2, r)
        )
    }
}

// region kokokara template dayo (^o^)
@Suppress("unused", "ClassName", "SpellCheckingInspection", "ConvertToStringTemplate", "MemberVisibilityCanBePrivate")
private class IO_abc174f(private val separator: String = System.lineSeparator()) {
    private val input = System.`in`
    private val buffer = ByteArray(1024)
    private var pointer = 0
    private var bufferLength = 0
    private val sb = StringBuilder()
    private fun Byte.isPrintable() = this in 33..126
    private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
    private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")

    private fun hasNextByte(): Boolean {
        return if (pointer < bufferLength) true else {
            pointer = 0
            bufferLength = input.read(buffer)
            bufferLength > 0
        }
    }

    private fun readByte(): Byte = if (hasNextByte()) buffer[pointer++] else -1
    private fun skipUnprintable() = run { while (hasNextByte() && !buffer[pointer].isPrintable()) pointer++ }
    private fun hasNext(): Boolean = run { skipUnprintable() }.run { hasNextByte() }
    private fun hasNextOrError() = if (!hasNext()) error("has no next element.") else Unit

    fun readString(): String {
        hasNextOrError()
        val sb = StringBuilder()
        var b = readByte()
        while (b.isPrintable()) {
            sb.appendCodePoint(b.toInt())
            b = readByte()
        }
        return sb.toString()
    }

    fun readLong(): Long {
        hasNextOrError()
        var n = 0L
        var negative = false
        var b = readByte()
        if (b == '-'.toByte()) {
            negative = true
            b = readByte()
        }
        if (!b.isNumeric()) error("$b is not numeric.")
        while (true) {
            when {
                b.isNumeric() -> n = n * 10 + b.toNumVal()
                b.toInt() == -1 || !b.isPrintable() -> return if (negative) -n else n
                else -> error("failed to parse. [n=$n, b=$b]")
            }
            b = readByte()
        }
    }

    fun readInt() = readLong()
        .let { if (it in Int.MIN_VALUE..Int.MAX_VALUE) it.toInt() else error("$it is not in range of Int.") }

    fun readDouble(): Double {
        var n = 0.0
        var div = 1.0
        var negative = false
        var b = readByte()
        if (b == '-'.toByte()) {
            negative = true
            b = readByte()
        }
        do n = n * 10 + b.toNumVal()
        while (run { b = readByte() }.run { b.isNumeric() })
        if (b == '.'.toByte()) {
            while (run { b = readByte() }.run { b.isNumeric() })
                n += b.toNumVal() / (run { div *= 10 }.run { div })
        }
        return if (negative) -n else n
    }

    fun readStringList(size: Int) = readList(size) { readString() }
    fun readIntList(size: Int) = readList(size) { readInt() }
    fun readLongList(size: Int) = readList(size) { readLong() }
    fun readDoubleList(size: Int) = readList(size) { readDouble() }
    fun readIntArray(size: Int) = IntArray(size) { readInt() }
    fun readLongArray(size: Int) = LongArray(size) { readLong() }
    fun readDoubleArray(size: Int) = DoubleArray(size) { readDouble() }
    inline fun <reified T> readArray(size: Int, init: () -> T) = Array(size) { init() }
    inline fun <T> readList(size: Int, init: () -> T) = List(size) { init() }

    fun println(): Unit = run { sb.append(separator) }
    fun print(any: Any): Unit = run { sb.append(any) }
    fun println(any: Any): Unit = run { sb.append(any.toString() + separator) }

    fun exec(code: IO_abc174f.() -> Unit) = run {
        Thread(null, { code() }, "(^o^)", 128 * 1024 * 1024).apply { start() }.join()
    }.run { kotlin.io.print(sb) }

    fun readLine(): Nothing = error("readLine is disabled.")
}
// endregion kokomade template dayo (^o^)


Measured memory_bytes: 174028