use std::fmt::Debug;
use std::str::FromStr;

pub struct TokenReader {
    reader: std::io::Stdin,
    tokens: Vec<String>,
    index: usize,
}

impl TokenReader {
    pub fn new() -> Self {
        Self {
            reader: std::io::stdin(),
            tokens: Vec::new(),
            index: 0,
        }
    }

    pub fn next<T>(&mut self) -> T
    where
        T: FromStr,
        T::Err: Debug,
    {
        if self.index >= self.tokens.len() {
            self.load_next_line();
        }
        self.index += 1;
        self.tokens[self.index - 1].parse().unwrap()
    }

    pub fn vector<T>(&mut self) -> Vec<T>
    where
        T: FromStr,
        T::Err: Debug,
    {
        if self.index >= self.tokens.len() {
            self.load_next_line();
        }
        self.index = self.tokens.len();
        self.tokens.iter().map(|tok| tok.parse().unwrap()).collect()
    }

    pub fn load_next_line(&mut self) {
        let mut line = String::new();
        self.reader.read_line(&mut line).unwrap();

        self.tokens = line.split_whitespace().map(String::from).collect();
        self.index = 0;
    }
}

#[derive(Clone, Copy)]
struct Query {
    index: usize,
    left: usize,
    right: usize,
    answer: usize,
}

impl Query {
    fn new(index: usize, left: usize, right: usize) -> Self {
        Self {
            index,
            left,
            right,
            answer: 0,
        }
    }
}

struct Fenwick {
    nodes: Vec<i32>,
}

impl Fenwick {
    fn new(len: usize) -> Self {
        Self {
            nodes: vec![0; len + 1],
        }
    }

    fn add(&mut self, mut pos: usize, val: i32) {
        while pos < self.nodes.len() {
            self.nodes[pos] += val;
            pos += Fenwick::lsb(pos);
        }
    }

    fn get(&mut self, mut pos: usize) -> i32 {
        let mut res = 0;
        while pos > 0 {
            res += self.nodes[pos];
            pos -= Fenwick::lsb(pos);
        }
        res
    }

    fn lsb(pos: usize) -> usize {
        let pos = pos as i32;
        (pos & -pos) as usize
    }
}

fn solve(colors: &Vec<usize>, queries: &mut Vec<Query>) {
    let mut prev = vec![None; colors.len() + 1];
    let mut dist = Fenwick::new(colors.len());

    queries.sort_by(|&a, &b| a.right.cmp(&b.right));
    let mut index = 0;

    for i in 0..colors.len() {
        if let Some(prev) = prev[colors[i]] {
            dist.add(prev, -1);
        }
        prev[colors[i]] = Some(i + 1);
        dist.add(i + 1, 1);

        while index < queries.len() && queries[index].right == i + 1 {
            let left = queries[index].left;
            let ans = dist.get(i + 1) - dist.get(left - 1);
            queries[index].answer = ans as usize;
            index += 1;
        }
    }
}

fn main() {
    let mut reader = TokenReader::new();
    let _ = reader.next::<usize>();
    let q = reader.next();
    let colors = reader.vector();

    let mut queries = Vec::with_capacity(q);
    for i in 0..q {
        let left = reader.next();
        let right = reader.next();
        queries.push(Query::new(i, left, right));
    }

    solve(&colors, &mut queries);
    queries.sort_by(|&a, &b| a.index.cmp(&b.index));

    for q in queries {
        println!("{}", q.answer);
    }
}


Measured memory_bytes: 44272