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

let INPUT = stdin

func scanInts(count: Int) -> [Int] {
    let format: String
    switch count {
    case 1: format = "%lld"
    case 2: format = "%lld%lld"
    case 3: format = "%lld%lld%lld"
    case 4: format = "%lld%lld%lld%lld"
    case 5: format = "%lld%lld%lld%lld%lld"
    case 6: format = "%lld%lld%lld%lld%lld%lld"
    default: format = String(repeating: "%lld", count: count)
    }
    let ptr = UnsafeMutablePointer<CLongLong>.allocate(capacity: count)
    let ptrArray = Array(ptr ..< ptr+count)
    let read = withVaList(ptrArray) {
        vfscanf(INPUT, format, $0)
    }
    assert(read == count)
    return ptrArray.map { Int($0.pointee) }
}
func scanInt() -> Int {
    scanInts(count: 1)[0]
}
func scanIntPair() -> (Int, Int) {
    let a: [Int] = scanInts(count: 2)
    return (a[0], a[1])
}
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)
}

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

func moSortQueries(_ unsorted: [(Int, Int)]) -> [(Int, (Int, Int))] {
    guard !unsorted.isEmpty else { return [] }
    
    var left = Int.max
    var right = Int.min
    for (l, r) in unsorted {
        assert(l < r)
        left = min(left, l)
        right = max(right, r)
    }
    let k = Int(Double(right-left).squareRoot())
    
    func compare(a: (Int, (Int, Int)), b: (Int, (Int, Int))) -> Bool {
        let a = a.1, b = b.1
        if a.0/k != b.0/k { return a.0 < b.0 }
        return (a.0/k % 2 == 0) ? (a.1 < b.1) : (a.1 > b.1)
    }
    
    var sorted = [(Int, Int)]()
    var indexMap = [Int]()
    sorted.reserveCapacity(unsorted.count)
    indexMap.reserveCapacity(unsorted.count)
    
    return unsorted.enumerated().sorted(by: compare)
}

func moQueryDiff(_ a: (Int, Int), _ b: (Int, Int)) -> (addList: [Int], removeList: [Int]) {
    var addList = [Int]()
    var removeList = [Int]()
    
    if a.0 < b.0 {
        removeList += a.0..<b.0
    } else {
        addList += (b.0..<a.0).reversed()
    }
    
    if a.1 < b.1 {
        addList += a.1..<b.1
    } else {
        removeList += (b.1..<a.1).reversed()
    }
    
    return (addList, removeList)
}

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

let (N, Q) = scanIntPair()
let c = scanInts(count: N)

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

var currentRange = (0, 0)
var currentMultiset = [Int: Int]()
for (i, q) in moSortQueries(queries) {
    let (addList, removeList) = moQueryDiff(currentRange, q)
    for j in addList {
        currentMultiset[c[j], default: 0] += 1
    }
    for j in removeList {
        currentMultiset[c[j]]! -= 1
        if currentMultiset[c[j]] == 0 {
            currentMultiset.removeValue(forKey: c[j])
        }
    }
    currentRange = q
    
    responses[i] = currentMultiset.count
}

for r in responses { print(r!) }
