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

m = Array.new(@n+1) {[]}
@n.times {|i| m[c[i]] << i + 1}

@f = Array.new(@n+1, 0)
def add(i, x)
    return if i == 0
    while i <= @n
        @f[i] += x
        i += i & -i
    end
end

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

m.each {|e| add(e[0], 1) if !e.empty?}

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

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