n, q = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = (0..n).map{|x|x&-x}
c = []
d = Array.new(n){[]}
q.times{|i|
	l, r = gets.split.map(&:to_i)
	d[r - 1] << [l - 1, i]
}
e = []
u = 0
n.times{|i|
	t = c[a[i]]
	while t && t <= n
		b[t] -= 1
		t += t & -t
	end
	t || u+=1
	c[a[i]] = i+1

	d[i].each{|x, y|
		s = u
		while x > 0
			s -= b[x]
			x &= x-1
		end
		e[y] = s
	}
}
puts e
