# after YouTube editorial

# Binary Indexed Tree (Fenwick Tree)
# https://youtu.be/lyHk98daDJo?t=7960

class BIT
  def initialize(x = 0)
    @n = x
    @d = Array.new(x+1,0)
  end

  def add(i, x = 1)
    i += 1
    while i <= @n
      @d[i] += x
      i += i & -i
    end
  end

  def sum(i)
    x = 0
    i += 1
    while i > 0
      x += @d[i]
      i -= i & -i
    end
    x
  end
end

n,q = gets.strip.split.map(&:to_i)
c = gets.strip.split.map(&:to_i)
pi = Array.new(n+1,-1)
ps = Array.new(n){[]}
n.times do |i|
  l = pi[c[i]]
  ps[l].push i if l != -1
  pi[c[i]] = i
end
qs = Array.new(n){[]}
q.times do |i|
  l,r = gets.strip.split.map(&:to_i)
  l -= 1
  r -= 1
  qs[l].push [r,i]
end
ans = Array.new(q)
d = BIT.new(n)
(n-1).downto(0) do |x|
  ps[x].each {|y| d.add(y,1)}
  qs[x].each {|qq|
    r = qq[0]
    i = qq[1]
    ans[i] = r - x + 1 - d.sum(r)
  }
end
ans.each {|e| p e}
