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

@f = Array.new(@n+1, 0)
def add(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

m = Array.new(@n)
h = Hash.new(-1)
(@n-1).downto(0) do |i|
    m[i] = h[c[i]]
    h[c[i]] = i
end

h.each {|k,v| add(v+1)}

klr = q.times.map {|i| [i] + gets.split.map(&:to_i)}.sort_by!{|k,l,r| l}
ans = Array.new(q)
memo = Array.new(@n+1)
i = 0
klr.each do |k,l,r|
    i.upto(l-2) {|j| add(m[j] + 1) if m[j] + 1 >= l}
    i = l - 1

    x = memo[l-1] or x = memo[l-1] = sum(l-1)
    ans[k] = sum(r) - x
end
puts ans
