#if os(Linux)
import Glibc
#else
import Darwin.C
#endif

let INPUT = stdin

var buffer: UnsafeMutablePointer<CChar>?
var bufferCapacity: Int32 = 0

func getsToBuffer(size: Int32) -> UnsafeMutablePointer<CChar> {
    if bufferCapacity < size {
        buffer?.deallocate()
        buffer = UnsafeMutablePointer.allocate(capacity: Int(size))
        bufferCapacity = size
    }
    return fgets(buffer!, size, INPUT)
}
func getIntFromBuffer(_ ptr: inout UnsafeMutablePointer<CChar>) -> Int {
    var minus = false
    var x: Int?
    while true {
        switch ptr.pointee {
        case 0x2D:
            assert(!minus && x == nil)
            minus = true
        case let d where (0x30...0x39).contains(d):
            x = (x ?? 0)*10 + Int(d)-0x30
        default:
            if x != nil { return minus ? -x! : x! }
        }
        ptr += 1
    }
}
func getInt() -> Int {
    var xPtr = getsToBuffer(size: 24)
    return getIntFromBuffer(&xPtr)
}
func getIntPair() -> (Int, Int) {
    var xPtr = getsToBuffer(size: 2*24)
    let x1 = getIntFromBuffer(&xPtr)
    let x2 = getIntFromBuffer(&xPtr)
    return (x1, x2)
}
func getInts(count: Int) -> [Int] {
    var xPtr = getsToBuffer(size: Int32(count) * 24)
    var a = [Int]()
    a.reserveCapacity(count)
    for _ in 0..<count { a.append(getIntFromBuffer(&xPtr)) }
    return a
}

func scanString(maxLength: Int = 255) -> String {
    let ptr = UnsafeMutablePointer<CChar>.allocate(capacity: maxLength+1)
    let read = withVaList([ptr]) {
        vfscanf(INPUT, "%\(maxLength)s", $0)
    }
    assert(read == 1)
    return String(cString: ptr)
}

//=============================================================================

struct FenwickTree<Element> {
    let count: Int
    private let defaultValue: Element
    private var tree: [Element]
    private let combine: (Element, _ adding: Element) -> Element
    private let inverse: (Element, _ removing: Element) -> Element

    init(count: Int,
         defaultValue: Element,
         addBy combine: @escaping (Element, _ adding: Element) -> Element,
         removeBy inverse: @escaping (Element, _ removing: Element) -> Element
    ) {
        tree = [Element](repeating: defaultValue, count: count)
        self.count = count
        self.defaultValue = defaultValue
        self.combine = combine
        self.inverse = inverse
    }

    mutating func update(at i: Int, adding value: Element) {
        assert(0 <= i && i < count)
        var i = i
        if i == 0 {
            tree[0] = combine(tree[0], value)
            return
        }
        repeat {
            tree[i] = combine(tree[i], value)
            i += i & -i  // increment LSB
        } while i < count
    }
    func query(range r: Range<Int>) -> Element {
        assert(0 <= r.lowerBound && r.upperBound <= count)
        var i = r.upperBound - 1
        var j = r.lowerBound - 1
        var sigma = defaultValue
        if i < 0 { return sigma }
        if j < 0 {
            sigma = combine(sigma, tree[0])
            j = 0
        }
        while i > j {
            sigma = combine(sigma, tree[i])
            i &= i-1  // decrement LSB
        }
        while j > i {
            sigma = inverse(sigma, tree[j])
            j &= j-1  // decrement LSB
        }
        return sigma
    }
}

//=============================================================================

let (N, Q) = getIntPair()
let c = getInts(count: N).map { $0 - 1 }

var queries = [(l: Int, r: Int)]()
queries.reserveCapacity(Q)
for _ in 1...Q {
    let (l, r) = getIntPair()
    queries.append((l: l-1, r: r-1+1))
}
var responses = [Int?](repeating: nil, count: Q)

var queue = queries.enumerated().sorted { $0.1.r > $1.1.r }
var lastSeen = [Int?](repeating: nil, count: N)
var counter = FenwickTree(count: N, defaultValue: 0, addBy: (+), removeBy: (-))

for (i, x) in c.enumerated() {
    if let j = lastSeen[x] {
        counter.update(at: j, adding: -1)
    }
    lastSeen[x] = i
    counter.update(at: i, adding: +1)

    while queue.last?.1.r == i+1 {
        let (queryId, q) = queue.removeLast()
        responses[queryId] = counter.query(range: q.l..<q.r)
    }
}

print(responses.map { String($0!) } .joined(separator: "\n"))


Measured memory_bytes: 68692