// -*- coding:utf-8-unix -*-
// based on the editorial PDF

use proconio::{fastout, input};
use Event::*;

#[fastout]
fn main() {
    input! {
        n: usize,
        q: usize,
        c: [usize; n],
        lr: [(usize, usize); q],
    }
    let mut goodballs_num: BinaryIndexedTree<isize, Additive> = BinaryIndexedTree::new(n);
    let mut goodballs_pos: Vec<Option<usize>> = vec![None; n];
    let mut events = Vec::new();
    for i in 1..=n {
        events.push(GoodBallMoved(c[i - 1], i));
    }
    for j in 1..=q {
        events.push(ColorNumQueried(j, lr[j - 1].0, lr[j - 1].1));
    }
    events.sort_unstable_by_key(|e| match *e {
        GoodBallMoved(_, p) => (p, 0),
        ColorNumQueried(_, _, r) => (r, 1),
    });
    let mut answers = Vec::new();
    for &e in &events {
        match e {
            GoodBallMoved(c, p) => {
                match goodballs_pos[c - 1] {
                    None => {}
                    Some(op) => {
                        goodballs_num.operate_to_index(op - 1, &(-1));
                    }
                }
                goodballs_pos[c - 1] = Some(p);
                goodballs_num.operate_to_index(p - 1, &(1));
            }
            ColorNumQueried(i, l, r) => {
                let answer = goodballs_num.query(l - 1..=r - 1);
                answers.push((i, answer));
            }
        }
    }
    answers.sort_unstable_by_key(|&(i, _)| i);
    for &(_, ans) in &answers {
        println!("{}", ans);
    }
}

#[derive(Copy, Debug, Clone)]
enum Event {
    GoodBallMoved(usize, usize),          // color, newposition
    ColorNumQueried(usize, usize, usize), // queryid, left, right
}

// BIT from https://github.com/rust-lang-ja/atcoder-rust-base/blob/ja-all-enabled/examples/abc157-e-proconio.rs
// It requires commutativity so that "plus" operation works
use alga::general::{AbstractGroupAbelian, Additive, Operator};
use std::marker::PhantomData;
use std::ops::{RangeInclusive, RangeTo, RangeToInclusive};

struct BinaryIndexedTree<A, O> {
    partial_sums: Vec<A>,
    phantom_operator: PhantomData<O>,
}

impl<A: AbstractGroupAbelian<O>, O: Operator> BinaryIndexedTree<A, O> {
    fn new(n: usize) -> Self {
        Self {
            partial_sums: vec![A::identity(); n],
            phantom_operator: PhantomData,
        }
    }

    fn operate_to_index(&mut self, i: usize, x: &A) {
        let mut i1 = i + 1;
        while i1 <= self.partial_sums.len() {
            self.partial_sums[i1 - 1] = self.partial_sums[i1 - 1].operate(x);
            // add "the last nonzero bit" to i1
            i1 += 1 << i1.trailing_zeros();
        }
    }
}

trait RangeQuery<T> {
    type Output;
    fn query(&self, r: T) -> Self::Output;
}

impl<A: AbstractGroupAbelian<O>, O: Operator> RangeQuery<RangeToInclusive<usize>>
    for BinaryIndexedTree<A, O>
{
    type Output = A;
    fn query(&self, range: RangeToInclusive<usize>) -> A {
        let mut sum = A::identity();
        let mut i1 = range.end + 1;
        while i1 > 0 {
            sum = sum.operate(&self.partial_sums[i1 - 1]);
            i1 -= 1 << i1.trailing_zeros();
        }
        return sum;
    }
}

impl<A: AbstractGroupAbelian<O>, O: Operator> RangeQuery<RangeTo<usize>>
    for BinaryIndexedTree<A, O>
{
    type Output = A;
    fn query(&self, range: RangeTo<usize>) -> A {
        if range.end == 0 {
            return A::identity();
        } else {
            return self.query(..=range.end - 1);
        }
    }
}

impl<A: AbstractGroupAbelian<O>, O: Operator> RangeQuery<RangeInclusive<usize>>
    for BinaryIndexedTree<A, O>
{
    type Output = A;
    fn query(&self, range: RangeInclusive<usize>) -> A {
        return self
            .query(..=*range.end())
            .operate(&self.query(..*range.start()).two_sided_inverse());
    }
}


Measured memory_bytes: 76332