N, Q = gets.split.map(&:to_i)

NC = Array.new(N) do
  Array.new(N, 0)
end

C = gets.split.map(&:to_i)

N.times do |i|
  NC.each do |a|
    a[i] = a[i - 1]
  end

  NC[C[i] - 1][i] += 1
end

Q.times do |i|
  c = 0
  l, r = gets.split.map(&:to_i)
  NC.each do |a|
    if (a[l - 1] != a[r - 1]) || ((l == 1) && (a[l - 1] == 1)) || ((l != 1) && (a[l - 1] != a[l - 2]))
      c += 1
    end
  end

  puts c
end
