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

s, ans, ds, m = 0, [], [], Array.new(N + 1, false)
LRs.map.with_index.sort_by{|(l, r), i| r}.each do |(l, r), i|
  (s + 1 .. r).each do |j|
    c = Cs[j]
    if k = m[c]
      ds << [k, j]
      m[c] = false
    else
      m[c] = j
    end
  end
  ans[i] = r - l + 1 - ds.count{|x, y| x >= l}
  s = r
end
puts ans