GC.disable

N, Q = gets.split.map(&:to_i)
Cs = [nil] + gets.split.map(&:to_i)
LRs = Q.times.map{gets.split.map(&:to_i)}

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

  def querry(i)
    r = 0
    while i > 0
      r += @b[i]
      i -= i & -i
    end
    r
  end

  def add(i, v)
    while i <= @n
      @b[i] += v
      i += i & -i
    end
  end
end

i, m, ans, b = 0, [], [], BIT.new(N)
LRs.map.with_index.sort_by{|(l, r), i| r}.each do |(l, r), q|
  (i + 1 .. r).each do |j|
    c = Cs[j]
    b.add(m[c], 1) if m[c]
    m[c] = j
  end
  i = r
  ans[q] = (r - l + 1) - b.querry(r) + b.querry(l - 1)
end
puts ans