#![allow(non_snake_case,unused_imports,dead_code)]
use std::str::FromStr;
use std::collections::{HashMap,HashSet,VecDeque,BinaryHeap};
use std::cmp::{max,min,Reverse,Ordering};
use std::time::{Duration, Instant};
use rand::Rng;

use proconio::input;
use proconio::marker::{Chars,Usize1,Isize1};

fn main() {

    input!{
        N:usize,
        Q:usize,
        C:[Usize1;N],
        LR:[(Usize1,Usize1);Q],
    }

    let mut LRI = LR.iter().enumerate().map(|lri| ((lri.1).0,(lri.1).1,lri.0)).collect::<Vec<_>>();
    LRI.sort_by_key(|x| (x.1,x.0));

    let INF = N+10;
    let mut ans = vec![0;Q];

    let mut T = SegmentTree::new(N,|x,y| x+y,0);
    let mut Prev = vec![INF;N];
    let mut Prev_tmp = vec![INF;N];

    for (i,&c) in C.iter().enumerate(){
        Prev[i] = Prev_tmp[c];
        Prev_tmp[c] = i;
    }

    let mut r0 = LRI[0].1 +1;
    for i in 0..r0{
        T.operate(i, 1);
        if Prev[i] != INF{
            T.operate(Prev[i],-1);
        }
    }
    for &(l,r,q) in &LRI{
        let r = r + 1;
        for i in r0..r{
            T.operate(i, 1);
            if Prev[i] != INF{
                T.operate(Prev[i],-1);
            }
        }
        ans[q] = T.get(l,r);

        r0 = r;
    }

    for out in ans{
        println!("{}",out);
    }

}

struct SegmentTree<N,F>
where F:Fn(&N,&N) ->N{
    n: usize,
    T: Vec<N>,
    func: F,
    identity: N,
}

impl<N:Clone,F> SegmentTree<N,F>
where F:Fn(&N,&N) ->N {
    fn new(n:usize,func:F,identity:N) -> SegmentTree<N,F>{
        let mut T = SegmentTree { n:n,T:Vec::new(),func:func,identity:identity};
        T.init();
        T
    }
    fn init(&mut self){
        self.n = 1<<format!("{:b}",self.n-1).len();
        self.T = vec![self.identity.clone(); 2*self.n-1];
    }
    fn _replace_without_update(&mut self,index:usize,value:N){
        let i = index + self.n - 1;
        self.T[i] = value;
    }
    fn replace(&mut self,index:usize,value:N){
        self._replace_without_update(index, value);
        let i = index + self.n - 1;
        self._update_parent((i-1)/2);
    }
    fn replace_range(&mut self,l:usize,r:usize,array:&Vec<N>){
        let n = array.len();
        let mut j = 0;
        for i in l..r{
            self._replace_without_update(i, array[j].clone());
            j = (j+1)%n;
        }
        self._update_range((l + self.n-2)/2,(r + self.n-2)/2);
    }
    fn _operate_without_update(&mut self,index:usize,value:N){
        let i = index + self.n - 1;
        self.T[i] = (self.func)(&self.T[i],&value);
    }
    fn operate(&mut self,index:usize,value:N){
        self._operate_without_update(index, value);
        let i = index + self.n - 1;
        self._update_parent((i-1)/2);
    }
    fn operate_range(&mut self,l:usize,r:usize,array:&Vec<N>){
        let n = array.len();
        let mut j = 0;
        for i in l..r{
            self._operate_without_update(i, array[j].clone());
            j = (j+1)%n;
        }
        self._update_range((l + self.n-2)/2,(r + self.n-2)/2);
    }
    fn _update(&mut self,i:usize){
        self.T[i] = (self.func)(&self.T[i*2+1],&self.T[i*2+2]);
    }
    fn _update_parent(&mut self,i:usize){
        self._update(i);
        if i>0 { self._update_parent((i-1)/2)}
    }
    fn _update_range(&mut self,l:usize,r:usize){
        for i in l..r{
            self._update(i);
        }
        if l<r{
            self._update_range((l-1)/2,(r-1)/2);
        }
    }
    fn get(&self,l:usize,r:usize) -> N{
    self._get(l,r,0,0,self.n)
    }
    fn _get(&self,l:usize,r:usize,i:usize,a:usize,b:usize) -> N{
        if l<=a && b<=r {
            self.T[i].clone()
        } else if b<=l || r<=a {
            self.identity.clone()
        } else{
            (self.func)(&self._get(l,r,2*i+1,a,(a+b)/2),
                        &self._get(l,r,2*i+2,(a+b)/2,b))
        }
    }
}

Measured memory_bytes: 50772