class SegTree
  def initialize(n)
    @offset = 1 << n.bit_length
    @data = Array.new(@offset * 2, 0)
  end
  def update(i, x)
    @data[@offset + i] = x
    j = (@offset + i) / 2
    while j > 0
      @data[j] = @data[2 * j] + @data[2 * j + 1]
      j /= 2
    end
    self
  end
  def range_sum(a, b, k = 1, l = 0, r = @offset)
    return 0 if r <= a || b <= l
    return @data[k] if a <= l && r <= b
    mid = (l + r) / 2
    return range_sum(a, b, 2 * k, l, mid) + range_sum(a, b, 2 * k + 1, mid, r)
  end
  def inspect
    @data[@offset, @offset].inspect
  end
end

N, M = gets.split.map(&:to_i)
C = gets.split.map(&:to_i)
Q = M.times.map{ gets.split.map(&:to_i) }

Ci = Array.new(N, 0)
A = Array.new(M)

st = SegTree.new(N + 1)
q = M.times.sort_by{|j| Q[j][1] }

(1 .. N).each do |i|
  c = C[i - 1]
  k = Ci[c]
  Ci[c] = i

  st.update(k, 0)
  st.update(i, 1)
  
  loop do
    break if q.empty?
    j = q[0]
    l,r = *Q[j]
    break if r > i
    q.shift
    A[j] = st.range_sum(l, r + 1)
  end
end
puts A
