@file:Suppress("NOTHING_TO_INLINE", "EXPERIMENTAL_FEATURE_WARNING", "OVERRIDE_BY_INLINE")
//@file:OptIn(ExperimentalStdlibApi::class)

import java.io.PrintWriter
import kotlin.math.*
import kotlin.random.Random
import kotlin.collections.sort as _sort
import kotlin.collections.sortDescending as _sortDescending
import kotlin.io.println as iprintln

/** @author Spheniscine */
fun main() { _writer.solve(); _writer.flush() }
fun PrintWriter.solve() {
//    val startTime = System.nanoTime()

    val numCases = 1//readInt()
    case@ for(case in 1..numCases) {
//        print("Case #$case: ")

        val n = readInt()
        val q = readInt()
        val C = IntArray(n) { readInt()-1 }

        val cqq = Array(n) { IntDeque() }
        repeat(n) { i ->
            cqq[C[i]].add(i)
        }

        val B = IntBIT(n)
        for(cq in cqq) {
            if(cq.isNotEmpty()) B.add(cq.remove(), 1)
        }

        val L = IntArray(q)
        val R = IntArray(q) { i ->
            L[i] = readInt()-1
            readInt()
        }

        val J = L.countSortIndices(n-1)
        val ans = IntArray(q)

        var i = 0
        for(l in 0 until n) {
            while(i < q && L[J[i]] == l) {
                val j = J[i]
                ans[j] = B.sum(R[j]-1)
                i++
            }
            B.add(l, -1)
            val cq = cqq[C[l]]
            if(cq.isNotEmpty()) B.add(cq.remove(), 1)
        }

        ans.forEach(::println)
    }

//    iprintln("Time: ${(System.nanoTime() - startTime) / 1000000} ms")
}

fun IntArray.countSortIndices(max: Int = max()!!): IntArray {
    val res = IntArray(size)
    val bkt = IntArray(max + 2)
    for(e in this) {
        bkt[e+1]++
    }
    for(i in 1 until bkt.lastIndex) {
        bkt[i] += bkt[i-1]
    }
    for(i in indices) {
        res[bkt[this[i]]++] = i
    }

    return res
}

inline fun IntArray.sortWith(cmp: (Int, Int) -> Int) {
    var len = 1
    val tmp = IntArray(size)
    while(len < size) {
        var l = 0
        while(true) {
            val m = l + len
            if(m >= size) break
            val r = min(size, m + len)

            var i = l
            var j = m

            for(k in l until r) {
                if(i != m && (j == r || cmp(this[i], this[j]) <= 0)) {
                    tmp[k] = this[i++]
                } else tmp[k] = this[j++]
            }
            l = r
        }
        for(i in 0 until l) this[i] = tmp[i]
        len += len
    }
}
inline fun <T: Comparable<T>> IntArray.sortBy(func: (Int) -> T) {
    sortWith { a, b -> func(a).compareTo(func(b)) }
}
inline fun <T: Comparable<T>> IntArray.sortByDescending(func: (Int) -> T) {
    sortWith { a, b -> func(b).compareTo(func(a)) }
}

class IntDeque(capacity: Int = 12){
    private var arr = IntArray(capacity)
    var size = 0
        private set
    inline val lastIndex get() = size - 1
    inline val indices get() = 0 until size

    private inline val capacity get() = arr.size

    inline fun isEmpty() = size == 0
    inline fun isNotEmpty() = size != 0

    private var head = 0

    private fun grow(minCapacity: Int = 8) {
        val newCapacity = maxOf(minCapacity, capacity + (capacity shr 1))
        val new = IntArray(newCapacity)
        for(i in 0 until size) new[i] = get(i)
        arr = new
        head = 0
    }

    private fun incHead() {
        head++
        if(head == capacity) head = 0
    }

    private fun decHead() {
        if(head == 0) head = capacity - 1
        else head--
    }

    private fun index(i: Int) = (head + i).let { if(it >= capacity) it - capacity else it }

    fun add(index: Int, element: Int) {
        if(size == capacity) grow()
        if(index < size / 2) {
            decHead()
            size++
            for(i in 0 until index) {
                set(i, get(i+1))
            }
        } else {
            size++
            for(i in size - 2 downTo index) {
                set(i+1, get(i))
            }
        }
        set(index, element)
    }

    fun addLast(e: Int) {
        if(size == capacity) grow()
        arr[index(size)] = e
        size++
    }
    inline fun add(e: Int) = addLast(e)

    val first get() = get(0)
    val last get() = get(lastIndex)

    fun removeFirst(): Int {
        val e = get(0)
        incHead()
        size--
        return e
    }
    inline fun remove() = removeFirst()
    fun removeLast(): Int {
        val e = get(lastIndex)
        size--
        return e
    }

    fun addFirst(e: Int) {
        if(size == capacity) grow()
        decHead()
        arr[head] = e
        size++
    }

    operator fun get(index: Int): Int {
        require(index in 0 until size)
        return arr[index(index)]
    }

    fun removeAt(index: Int): Int {
        val e = get(index)
        if(index < size / 2) {
            for(i in index - 1 downTo 0) {
                set(i+1, get(i))
            }
            incHead()
        } else {
            for(i in index until size - 1) {
                set(i, get(i+1))
            }
        }
        size--
        return e
    }

    operator fun set(index: Int, element: Int): Int {
        val old = get(index)
        arr[index(index)] = element
        return old
    }

    operator fun iterator() = object: IntIterator() {
        var i = 0
        override fun hasNext(): Boolean = i < size
        override fun nextInt(): Int = get(i++)
    }
}

class IntBIT(val size: Int) {
    private val A = IntArray(size + 1)

    // zeroes all the bits except the least significant one
    private inline fun lsb(i: Int) = i and -i

    fun sum(end: Int): Int {
        var i = minOf(end + 1, size) // BIT is internally 1-indexed
        var sum = 0
        while(i > 0) {
            sum += A[i]
            i -= lsb(i)
        }
        return sum
    }

    fun sum(start: Int, endx: Int) = sum(endx - 1) - sum(start - 1)
    fun sum(range: IntRange) = sum(range.last) - sum(range.first - 1)

    fun add(index: Int, value: Int) {
        var i = index + 1 // BIT is internally 1-indexed
        while(i <= size) {
            A[i] += value
            i += lsb(i)
        }
    }

    private val hsb = Integer.highestOneBit(size)

    fun lowerBound(value: Int): Int {
        var sum = 0
        var pos = 0

        var i = hsb
        while(i > 0) {
            val npos = pos + i
            if (npos <= size) {
                val nsum = sum + A[npos]
                if(nsum < value) { // for upper bound, replace with <=
                    sum = nsum
                    pos = npos
                }
            }
            i = i shr 1
        }

        return pos
    }
}

/** IO */
//@JvmField val INPUT = File("input.txt").inputStream()
//@JvmField val OUTPUT = File("output.txt").outputStream()
@JvmField val INPUT = System.`in`
@JvmField val OUTPUT = System.out

const val _BUFFER_SIZE = 1 shl 16
@JvmField val _buffer = ByteArray(_BUFFER_SIZE)
@JvmField var _bufferPt = 0
@JvmField var _bytesRead = 0

tailrec fun readChar(): Char {
    if(_bufferPt == _bytesRead) {
        _bufferPt = 0
        _bytesRead = INPUT.read(_buffer, 0, _BUFFER_SIZE)
    }
    return if(_bytesRead < 0) Char.MIN_VALUE
    else {
        val c = _buffer[_bufferPt++].toChar()
        if (c == '\r') readChar()
        else c
    }
}

fun readLine(): String? {
    var c = readChar()
    return if(c == Char.MIN_VALUE) null
    else buildString {
        while(c != '\n' && c != Char.MIN_VALUE) {
            append(c)
            c = readChar()
        }
    }
}
fun readLn() = readLine()!!

fun read() = buildString {
    var c = readChar()
    while(c <= ' ') {
        if(c == Char.MIN_VALUE) return@buildString
        c = readChar()
    }
    do {
        append(c)
        c = readChar()
    } while(c > ' ')
}
fun readInt() = read().toInt()
fun readDouble() = read().toDouble()
fun readLong() = read().toLong()
fun readStrings(n: Int) = List(n) { read() }
fun readLines(n: Int) = List(n) { readLn() }
fun readInts(n: Int) = List(n) { read().toInt() }
fun readIntArray(n: Int) = IntArray(n) { read().toInt() }
fun readDoubles(n: Int) = List(n) { read().toDouble() }
fun readDoubleArray(n: Int) = DoubleArray(n) { read().toDouble() }
fun readLongs(n: Int) = List(n) { read().toLong() }
fun readLongArray(n: Int) = LongArray(n) { read().toLong() }

@JvmField val _writer = PrintWriter(OUTPUT, false)

/** shuffles and sort overrides to avoid quicksort attacks */
private inline fun <T> _shuffle(rnd: Random, get: (Int) -> T, set: (Int, T) -> Unit, size: Int) {
    // Fisher-Yates shuffle algorithm
    for (i in size - 1 downTo 1) {
        val j = rnd.nextInt(i + 1)
        val temp = get(i)
        set(i, get(j))
        set(j, temp)
    }
}

@JvmField var _random: Random? = null
val random get() = _random ?: Random(0x594E215C123 * System.nanoTime()).also { _random = it }

fun IntArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
fun IntArray.sort() { shuffle(); _sort() }
fun IntArray.sortDescending() { shuffle(); _sortDescending() }

fun LongArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
fun LongArray.sort() { shuffle(); _sort() }
fun LongArray.sortDescending() { shuffle(); _sortDescending() }

fun DoubleArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
fun DoubleArray.sort() { shuffle(); _sort() }
fun DoubleArray.sortDescending() { shuffle(); _sortDescending() }

fun CharArray.shuffle(rnd: Random = random) = _shuffle(rnd, ::get, ::set, size)
inline fun CharArray.sort() { _sort() }
inline fun CharArray.sortDescending() { _sortDescending() }

inline fun <T: Comparable<T>> Array<out T>.sort() = _sort()
inline fun <T: Comparable<T>> Array<out T>.sortDescending() = _sortDescending()
inline fun <T: Comparable<T>> MutableList<out T>.sort() = _sort()
inline fun <T: Comparable<T>> MutableList<out T>.sortDescending() = _sortDescending()

fun `please stop removing these imports IntelliJ`() { iprintln(max(1, 2)) }

/** additional commons */
inline fun <T> Iterable<T>.sumByLong(func: (T) -> Long) = fold(0L) { acc, t -> acc + func(t) }
inline fun <T> Sequence<T>.sumByLong(func: (T) -> Long) = fold(0L) { acc, t -> acc + func(t) }
inline fun <T> Array<T>.sumByLong(func: (T) -> Long) = fold(0L) { acc, t -> acc + func(t) }
fun IntArray.sumLong() = fold(0L, Long::plus)


Measured memory_bytes: 128164