import java.io.*
import java.util.*
import java.lang.*
import java.lang.Math.*


class BIT(val N: Int) {
    var sg = LongArray(0)
    init {
        sg = LongArray(N+1){0L}
    }
    private fun sum1(I: Int): Long {
        var res = 0L
        var i = I
        while (i > 0) {
            res += sg[i]
            i -= i and -i
        }
        return res
    }
    fun add(I: Int, X: Long) {
        var i = I+1
        while(i <= N) {
            sg[i] += X
            i += i and -i
        }
    }
    fun sum(i: Int, j: Int): Long {
        return sum1(j) - sum1(i)
    }
    operator fun get(i: Int): Long {
        return sum(i, i+1)
    }
}

data class Query(val id: Int, val l: Int, val r: Int) {}

fun solve() {
    val (N, Q) = rd.readIntArray()
    val C = rd.readIntArray().map{ it - 1 }
    assert(C.size == N){"C.size == N"}
    val qrys = ArrayList<Query>()
    for (id in 0 until Q) {
        var (l, r) = rd.readIntArray()
        l--; r--
        qrys.add(Query(id, l, r))
    }
    qrys.sortBy{ it.r }

    val lastIdx = IntArray(N){-1}
    val bit = BIT(N)
    var q = 0
    val ans = Array(Q){0L}
    for (x in 0 until N) {
        if (lastIdx[C[x]] < 0) {
            lastIdx[C[x]] = x
            bit.add(x, 1)
        } else {
            val px = lastIdx[C[x]]
            lastIdx[C[x]] = -1
            bit.add(px, -1)
            lastIdx[C[x]] = x
            bit.add(x, 1)
        }

        while (q<Q && qrys[q].r == x) {
            val qry = qrys[q++]

            ans[qry.id] = bit.sum(qry.l, qry.r+1)
        }
    }

    println(ans.joinToString("\n"))

    return
}


//val rd = debug.Reader("abc", "174", "f", "sample-1")
val rd = Reader()


fun main(args: Array<String>) {
    try {
        var exception: Throwable? = null
        val sth = Thread(null, SolveThread(), "solveThread", 128 * 1024 * 1024)
        sth.setUncaughtExceptionHandler { _, e -> exception = e }
        sth.start(); sth.join()
        if (exception != null) throw exception!!
    } catch (e: Exception) { throw e }
}
const val MOD = 1_000_000_007L; const val INF = Int.MAX_VALUE/2; const val LINF = Long.MAX_VALUE/2
const val EPS = 1e-9; fun DBLEQ(a: Double, b: Double): Boolean {return abs(a - b) < EPS}
data class IntPair(val first: Int, val second: Int)
data class To(val idx: Int, val cost: Long, val col: Int)
fun <T>edge(V: Int): Array<ArrayList<T>> { return Array(V){ArrayList<T>()} }
val errPrintln: (Any) -> Unit = { msg -> System.err.println(msg) }
fun rAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("EAssert Error: $msg"); throw Error(msg) }
}
fun tAssert(exp: Boolean, lazyMsg: () -> String = {""}) {
    if (!exp) { val msg = lazyMsg(); errPrintln("TAssert Error: $msg"); Thread.sleep(3000) }
}
class SolveThread : Runnable {
    override fun run() { solve() }
}
class Reader {
    private val br = BufferedReader(InputStreamReader(System.`in`))
    val readString: () -> String = { br.readLine() }
    val readInt: () -> Int = { br.readLine().toInt() }
    val readLong: () -> Long = { br.readLine().toLong() }
    val readIntArray: () -> IntArray = { br.readLine().split(' ').map { it.toInt() }.toIntArray() }
    val readLongArray: () -> LongArray = { br.readLine().split(' ').map { it.toLong() }.toLongArray() }
    val readListInt: () -> List<Int> = { br.readLine().split(' ').map { it.toInt() } }
    val readListLong: () -> List<Long> = { br.readLine().split(' ').map { it.toLong() } }
}


Measured memory_bytes: 125508