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[l-1] << [r-1, i]
}

nxt = Array.new(N)
wk = Array.new(N)
if C.uniq.size > N/2 then
  bit = BinaryIndexedTree.new(N, 1)
  C.each_with_index{|c, i|
    (bit.add(i, -1); nxt[wk[c-1]] = i) if not wk[c-1].nil?
    wk[c-1] = i
  }
else
  bit = BinaryIndexedTree.new(N, 0)
  cnt = Array.new(N, 1)
  C.each_with_index{|c, i|
    (cnt[i] = 0; nxt[wk[c-1]] = i) if not wk[c-1].nil?
    wk[c-1] = i
  }
  cnt.each_with_index{|c, i| bit.add(i, 1) if c == 1}
end
ans = Array.new(N)
QU.each_with_index{|l, j|
  l.each{|r, i|
    ans[i] = bit.sum(r) - j
  }
  bit.add(nxt[j], 1) if not nxt[j].nil?
}

puts ans
