Distinct Values - Implementation

Here's the full solution:

function solve(arr, queries)
    // Coordinate compress values to [0, n)
    compress(arr)

    B := floor(sqrt(n)) + 1
    sort queries by (floor(l / B), r)

    cnt := array of size n, initialized to 0
    distinctCount := 0
    currentL := 0
    currentR := -1
    answers := array of size q

    for each (l, r, index) in queries
        while currentR < r
            currentR := currentR + 1
            add(arr[currentR])
        while currentL > l
            currentL := currentL - 1
            add(arr[currentL])
        while currentR > r
            remove(arr[currentR])
            currentR := currentR - 1
        while currentL < l
            remove(arr[currentL])
            currentL := currentL + 1
        answers[index] := distinctCount

    return answers

Time: $O((n + q)\sqrt{n})$. Space: $O(n)$.