n, q = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)

class FeTree
    def initialize(n)
        @n = n
        @f = Array.new(@n+1,0)
    end

    def add1(i)
        while i <= @n
            @f[i] += 1
            i += i & -i
        end
    end

    def sum(i)
        s = 0
        while i > 0
            s += @f[i]
            i &= i-1
        end
        s
    end
end

klr = q.times.map {|i| [i] + gets.split.map(&:to_i)}.sort_by!{|k,l,r| r}
f = FeTree.new(n)
m = Array.new(n)
ans = Array.new(q)
i = 0
klr.each do |k,l,r|
    while i < r
        f.add1(m[c[i]]) if m[c[i]]
        m[c[i]] = i += 1
    end

    ans[k] = r - l + 1 - f.sum(r) + f.sum(l-1)
end

puts ans