class BinaryIndexedTree
  def initialize(a)
    @n = a.size
    @b = Array.new(@n, 0)
    a.each_with_index{|aa, i| add(i, aa) if aa > 0}
  end
  def add(i, x)
    i += 1
    while i <= @n do
      @b[i-1] += x
      i += i&-i
    end
  end
  def sum(i)
    i+= 1
    ret = 0
    while i > 0 do
      ret += @b[i-1]
      i -= i&-i
    end
    ret
  end
end

N, Q = gets.chomp.split(" ").map(&:to_i)
C = gets.chomp.split(" ").map(&:to_i)
QU = Q.times.map{|i| gets.chomp.split(" ").map(&:to_i) << i}.sort_by{|l, r, i| l}

cnt = Array.new(N, 1)
nxt = Array.new(N)
wk = Array.new(N)
C.each_with_index{|c, i|
  (cnt[i] = 0; nxt[wk[c-1]] = i) if not wk[c-1].nil?
  wk[c-1] = i
}
bit = BinaryIndexedTree.new(cnt)
wk = 0
ans = Array.new(N)
QU.each{|l, r, i|
  while wk < l-1
    bit.add(nxt[wk], 1) if not nxt[wk].nil?
    wk += 1
  end
  ans[i] = bit.sum(r-1) - l + 1
}

puts ans*?\n
