Scanf.scanf "%d %d" (fun n q ->
    let c = Array.init n (fun _ -> Scanf.scanf " %d" (fun a -> a)) in
    let queries = Array.init q (fun i -> Scanf.scanf " %d %d" (fun l r -> r - 1, l - 1, i)) in
    Array.sort compare queries;
    let ans = Array.make q 0 in

    let bit = Array.make (n + 1) 0 in
    let last_visit = Array.make 500001 (-1) in

    let ll  (r, l, i) = l in
    let rr  (r, l, i) = r in
    let idx (r, l, i) = i in

    let update index v =
        let rec loop ii =
            if ii <= n then (
                bit.(ii) <- bit.(ii) + v;
                loop (ii + (ii land (-ii)))
            )
        in
        loop index
    in
    let query index =
        let rec loop ii sum =
            if ii > 0 then (
                loop (ii - (ii land (-ii))) (sum + bit.(ii))
            ) else sum
        in
        loop index 0
    in

    let rec loop i query_counter =
        if i < n then (
            if last_visit.(c.(i)) <> -1 then
                update (last_visit.(c.(i)) + 1) (-1);
            last_visit.(c.(i)) <- i;
            update (i + 1) 1;

            let rec loop2 query_counter =
                if query_counter < q && rr queries.(query_counter) = i then  (
                    ans.(idx queries.(query_counter)) <-
                        query (rr queries.(query_counter) + 1) - query (ll queries.(query_counter));
                    loop2 (query_counter + 1)
                ) else query_counter
            in
            let query_counter = loop2 query_counter in
            loop (i + 1) query_counter
        )
    in
    loop 0 0;
    Array.iter (Printf.printf "%d\n") ans;
)
