N,Q = gets.split.map &:to_i
C = gets.split.map &:to_i

q = Q.times.map do |i| 
    l,r = gets.split.map(&:to_i)
    [l-1,r-1,i]
end
    
q.sort_by!{|l,r,i| r}

$BIT = [0]*(N+1)

def add(x)
    while x<=N
        $BIT[x] += 1
        x += x & -x
    end
end

def sum(x)
    s = 0
    while x>0
        s += $BIT[x]
        x -= x & -x
    end
    s
end

ans = [-1]*Q
csr = 0
last = [nil]*N
q.each do |l,r,idx|
    while csr<=r
        c = C[csr]
        add(last[c]+1) if last[c]

        last[c] = csr
        csr += 1
    end

    ans[idx] = (r-l+1) - (sum(r+1) - sum(l))
end

puts ans