#![allow(unused_imports)]
#![allow(unused_macros)]
use std::cmp::{max, min, Ordering::*};
use std::collections::*;
use std::io::{stdin, Read};

#[allow(unused_macros)]
macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, $var:ident $($r:tt)*) => {
        let $var = parse_val!($it, usize);
        parse!($it $($r)*);
    };
}

#[allow(unused_macros)]
macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: tt),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, u1) => {
        $it.next().unwrap().parse::<usize>().unwrap() -1
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

#[cfg(debug_assertions)]
macro_rules! debug {
    ($( $args:expr ),*) => { eprintln!( $( $args ),* ); }
}

#[cfg(not(debug_assertions))]
macro_rules! debug {
    ($( $args:expr ),*) => {
        ()
    };
}

pub struct CountLessThan<T> {
    dat: Vec<Vec<T>>,
    n: usize,
}

impl<T: Ord + Copy> CountLessThan<T> {
    pub fn new(v: Vec<T>) -> Self {
        let n = v.len();
        let mut dat = vec![vec![]; 2 * n];
        for (i, &vi) in v.iter().enumerate() {
            dat[n + i].push(vi);
        }
        // merge
        for k in (1..n).rev() {
            dat[k] = dat[2 * k].clone();
            let mut tmp = dat[2 * k + 1].clone();
            dat[k].append(&mut tmp);
            dat[k].sort();
        }
        Self { dat: dat, n: n }
    }
    pub fn get(&self, l: usize, r: usize, query: T) -> usize {
        let mut l = l + self.n;
        let mut r = r + self.n;
        let mut countr = 0;
        let mut countl = 0;
        let cmp = |x: &T| match x.cmp(&query) {
            Equal => Less,
            d => d,
        };
        while l < r {
            if l & 1 != 0 {
                countl += self.dat[l].binary_search_by(cmp).unwrap_or_else(|x| x);
                l += 1;
            }
            if r & 1 != 0 {
                countr += self.dat[r - 1].binary_search_by(cmp).unwrap_or_else(|x| x);
            }
            l >>= 1;
            r >>= 1;
        }
        countl + countr
    }
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse!(it, n: usize, q: usize, c: [usize; n]);
    let mut nxt = vec![n; n];
    let mut last = HashMap::new();
    for i in (0..n).rev() {
        let e = last.entry(c[i]).or_insert(n);
        nxt[i] = *e;
        *e = i;
    }
    let cs = CountLessThan::new(nxt);
    for _ in 0..q {
        parse!(it, l: u1, r: u1);
        let c = cs.get(l, r + 1, r);
        println!("{}", r + 1 - l - c);
    }
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 162808