class BinaryIndexedTree
  def initialize(n, d)
    @n = n
    if d == 0 then
      @b = Array.new(@n, 0)
    else
      @b = (1..@n).map{|x| (x&-x)*d}
    end
  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 = Array.new(N){[]}
Q.times{|i|
  l, r = gets.chomp.split(" ").map(&:to_i)
  QU[r-1] << [l-1, i]
}

nxt = Array.new(N)
wk = Array.new(N)
bit = BinaryIndexedTree.new(N, 1)
ans = Array.new(N)
QU.each_with_index{|w, r|
  bit.add(N-1-wk[C[r]], -1) if not wk[C[r]].nil?
  wk[C[r]] = r
  w.each{|l, i|
    ans[i] = bit.sum(N-1-l) - (N-1-r)
  }
}

puts ans
