AtCoder Beginner Contest 174 - Range Set Query

We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.
You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

-----Constraints-----
 - 1\leq N,Q \leq 5 \times 10^5
 - 1\leq c_i \leq N
 - 1\leq l_i \leq r_i \leq N
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q

-----Output-----
Print Q lines. The i-th line should contain the response to the i-th query.

-----Sample Input-----
4 3
1 2 1 3
1 3
2 4
3 3

-----Sample Output-----
2
3
1

 - The 1-st, 2-nd, and 3-rd balls from the left have the colors 1, 2, and 1 - two different colors.
 - The 2-st, 3-rd, and 4-th balls from the left have the colors 2, 1, and 3 - three different colors.
 - The 3-rd ball from the left has the color 1 - just one color.

Source: atcoder | Difficulty: MEDIUM_HARD


Solutions:
import sys
input = sys.stdin.readline

def BIT_query(BIT, idx):
	res_sum = 0
	if idx == 0:
		return 0
	while idx > 0:
		res_sum += BIT[idx]
		idx -= idx & -idx
	return res_sum

def BIT_update(BIT, idx, x, n):
	while idx <= n:
		BIT[idx] += x
		idx += idx & -idx
	return

def main():
	(N, Q) = map(int, input().split())
	C = list(map(int, input().split()))
	LRI = []
	for i in range(Q):
		(l, r) = map(int, input().split())
		LRI.append((r, l, i))
	LRI.sort(key=lambda x: x[0])
	lastAppend = [-1] * (N + 1)
	BIT = [0] * (N + 1)
	ANS = [0] * Q
	now = 1
	for (r, l, i) in LRI:
		while now <= r:
			c = C[now - 1]
			if lastAppend[c] == -1:
				BIT_update(BIT, now, 1, N)
			else:
				BIT_update(BIT, now, 1, N)
				BIT_update(BIT, lastAppend[c], -1, N)
			lastAppend[c] = now
			now += 1
		ANS[i] = BIT_query(BIT, r) - BIT_query(BIT, l - 1)
	for ans in ANS:
		print(ans)
main()


import sys
input = sys.stdin.readline

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0 for _ in range(n + 2)]

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
rli = []
for i in range(q):
	(l, r) = map(int, input().split())
	rli.append((r, l, i))
rli.sort(key=lambda x: x[0])
last = [-1 for _ in range(n + 1)]
bit = Bit(n)
ans = [-1 for _ in range(q)]
cur = 1
for (r, l, i) in rli:
	for j in range(cur, r + 1):
		if last[c[j - 1]] != -1:
			bit.add(last[c[j - 1]], -1)
		last[c[j - 1]] = j
		bit.add(j, 1)
	cur = r + 1
	ans[i] = bit.sum(r) - bit.sum(l - 1)
print(*ans, sep='\n')


import sys
input = sys.stdin.readline

def update(index, value, bit):
	while index < len(bit):
		bit[index] += value
		index += index & -index

def cumsum(index, bit):
	ans = 0
	while index > 0:
		ans += bit[index]
		index -= index & -index
	return ans

def main():
	(N, q) = [int(x) for x in input().split()]
	C = [int(x) - 1 for x in input().split()]
	Q = []
	for i in range(q):
		(l, r) = [int(x) - 1 for x in input().split()]
		Q.append((i, l, r))
	Q.sort(key=lambda x: x[2])
	leftmost = [-1] * N
	bit = [0] * (N + 1)
	prev = -1
	ans = [0] * q
	for (i, l, r) in Q:
		to_update = {}
		for x in range(prev + 1, r + 1):
			to_update[C[x]] = x
		for (c, x) in to_update.items():
			if leftmost[c] >= 0:
				update(leftmost[c] + 1, -1, bit)
			leftmost[c] = x
			update(x + 1, 1, bit)
		prev = r
		ans[i] = cumsum(r + 1, bit) - cumsum(l, bit)
	for a in ans:
		print(a)
main()


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
l = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
	l[i].append(i)
l.sort(key=lambda x: x[1])
L = [-1] * (5 * 10 ** 5 + 1)

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)
		self.depth = n.bit_length()

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
BIT = Bit(n + 1)
ans = [0] * q
ct = 0
for i in range(q):
	while ct <= l[i][1]:
		if L[c[ct - 1] - 1] != -1:
			BIT.add(L[c[ct - 1] - 1], -1)
		L[c[ct - 1] - 1] = ct + 1
		BIT.add(ct + 1, 1)
		ct += 1
	ans[l[i][2]] = BIT.sum(l[i][1] + 1) - BIT.sum(l[i][0])
for i in range(q):
	print(ans[i])


def main():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	(*C,) = map(int, input().split())
	last = [-1] * (N + 1)
	P = [[] for _ in [0] * (N + 1)]
	for (i, c) in enumerate(C):
		if last[c] != -1:
			P[last[c]].append(i + 1)
		last[c] = i + 1
	queries = [[] for _ in [0] * (N + 1)]
	indices = [[] for _ in [0] * (N + 1)]
	for i in range(Q):
		(l, r) = map(int, input().split())
		queries[l].append(r)
		indices[l].append(i)

	def add(A, i, x):
		while i <= N:
			A[i] += x
			i += i & -i

	def sum(A, i):
		ret = 0
		while i:
			ret += A[i]
			i ^= i & -i
		return ret
	A = [0] * (N + 1)
	ans = [0] * Q
	for l in range(N, 0, -1):
		for cr in P[l]:
			add(A, cr, 1)
		for (i, r) in zip(indices[l], queries[l]):
			ans[i] = r - l + 1 - sum(A, r)
	print(*ans, sep='\n')
main()


class BinaryIndexedTree:

	def __init__(self, n):
		self.bit = [0] * n

	def add(self, i, x):
		i += 1
		while i <= len(self.bit):
			self.bit[i - 1] += x
			i += i & -i

	def sum_sub(self, i):
		a = 0
		i += 1
		while i:
			a += self.bit[i - 1]
			i -= i & -i
		return a

	def sum(self, i, j):
		a = self.sum_sub(j + 1)
		if i != 0:
			a -= self.sum_sub(i - 1)
		return a
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
ans = [0] * q
queries = [[] for _ in range(n)]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	queries[r].append((l, i))
lastAppeared = [-1] * n
bitt = BinaryIndexedTree(n)
j = 0
for i in range(n):
	if lastAppeared[a[i] - 1] != -1:
		bitt.add(lastAppeared[a[i] - 1], -1)
		bitt.add(i, 1)
		lastAppeared[a[i] - 1] = i
	else:
		bitt.add(i, 1)
		lastAppeared[a[i] - 1] = i
	for (l, ind) in queries[i]:
		ans[ind] = bitt.sum(l, i - 1)
print(*ans)


(n, q) = map(int, input().split())
bit = [0] * (n + 4)

def add(a, i):
	while i <= n:
		bit[i] += a
		i += i & -i

def query(i):
	res = 0
	while i > 0:
		res += bit[i]
		i -= i & -i
	return res
a = list(map(int, input().split()))
la = [-1] * n
li = [list(map(int, input().split())) + [_] for _ in range(q)]
li.sort(key=lambda x: x[1])
idx = 0
ans = [0] * q
for (l, r, xxx) in li:
	l -= 1
	for i in range(idx, r):
		if la[a[i] - 1] == -1:
			add(1, i + 1)
		else:
			add(-1, la[a[i] - 1] + 1)
			add(1, i + 1)
		la[a[i] - 1] = i
	idx = r
	ans[xxx] = query(r) - query(l)
for res in ans:
	print(res)


import sys
input = sys.stdin.buffer.readline
(N, Q) = map(int, input().split())
BIT = [0] * (N + 1)

def BIT_query(idx):
	res_sum = 0
	while idx > 0:
		res_sum += BIT[idx]
		idx -= idx & -idx
	return res_sum

def BIT_update(idx, x):
	while idx <= N:
		BIT[idx] += x
		idx += idx & -idx
	return
c = [-1] + list(map(int, input().split()))
lastAppeared = [-1] * (N + 1)
ans = [0] * Q
queries = []
for q in range(Q):
	(l, r) = map(int, input().split())
	queries.append(r * 10 ** 12 + l * 10 ** 6 + q)
queries.sort()
curR = 0
for i in range(Q):
	query = queries[i]
	r = query // 10 ** 12
	query %= 10 ** 12
	l = query // 10 ** 6
	q = query % 10 ** 6
	while curR < r:
		curR += 1
		new = c[curR]
		last = lastAppeared[new]
		if last != -1:
			BIT_update(last, -1)
		lastAppeared[new] = curR
		BIT_update(curR, 1)
	ans[q] = BIT_query(r) - BIT_query(l - 1)
for i in range(Q):
	print(ans[i])


def main():
	import sys
	input = sys.stdin.readline

	class BIT:

		def __init__(self, n):
			self.size = n
			self.tree = [0] * (n + 1)

		def add(self, i, x):
			while i <= self.size:
				self.tree[i] += x
				i += i & -i

		def sum(self, i):
			s = 0
			while i > 0:
				s += self.tree[i]
				i -= i & -i
			return s
	(N, Q) = map(int, input().split())
	C = list(map(int, input().split()))
	LR = []
	for i in range(Q):
		(l, r) = map(int, input().split())
		LR.append((l, r, i))
	bit = BIT(N)
	color = [0] * (N + 1)
	ANS = [0] * Q
	LR.sort(key=lambda x: x[1])
	cur = 1
	for (l, r, j) in LR:
		for i in range(cur, r + 1):
			c = C[i - 1]
			if color[c] != 0:
				bit.add(color[c], -1)
			color[c] = i
			bit.add(i, 1)
		cur = r + 1
		ANS[j] = bit.sum(r) - bit.sum(l - 1)
	for a in ANS:
		print(a)
main()


from operator import itemgetter
import sys

def read():
	return sys.stdin.readline().rstrip()

def add(arr, i, x):
	while i < len(arr):
		arr[i] += x
		i += i & -i

def range_sum(arr, a, b):
	s = 0
	i = b
	while i > 0:
		s += arr[i]
		i -= i & -i
	i = a - 1
	while i > 0:
		s -= arr[i]
		i -= i & -i
	return s

def main():
	(n, q) = map(int, read().split())
	c = [int(i) - 1 for i in read().split()]
	queries = [(0, 0, 0) for _ in range(q)]
	for i in range(q):
		(l, r) = map(int, read().split())
		queries[i] = (i, l, r)
	queries = iter(sorted(queries, key=itemgetter(2)))
	last = [0] * n
	bit = [0] * (n + 1)
	ans = [-1] * q
	(k, l, r) = next(queries)
	for i in range(n):
		ci = c[i]
		li = last[ci]
		if li > 0:
			add(bit, li, -1)
		last[ci] = i + 1
		add(bit, i + 1, 1)
		while i + 1 == r:
			ans[k] = range_sum(bit, l, r)
			try:
				(k, l, r) = next(queries)
			except StopIteration:
				break
	print(*ans, sep='\n')
main()


import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, a):
		self.n = len(a)
		self.a = [0] * (self.n + 1)
		for (i, j) in enumerate(a):
			self.update(i, j)

	def update(self, i, x):
		i += 1
		while i <= self.n:
			self.a[i] = self.a[i] + x
			i += i & -i

	def get(self, i):
		s = 0
		i += 1
		while i != 0:
			s = s + self.a[i]
			i -= i & -i
		return s

def inmin(x):
	return int(x) - 1
(n, q) = map(int, input().split())
c = list(map(inmin, input().split()))
que = [[i, list(map(inmin, input().split()))] for i in range(q)]
que.sort(key=lambda x: x[1][1])
ans = [0] * q
last = [-1] * n
bit = BIT([0] * (n + 10))
j = 0
for i in range(n):
	if last[c[i]] >= 0:
		bit.update(last[c[i]] + 5, -1)
	bit.update(i + 5, 1)
	last[c[i]] = i
	while j < q and que[j][1][1] == i:
		ans[que[j][0]] = bit.get(i + 5) - bit.get(que[j][1][0] + 4)
		j += 1
print(*ans)


import sys
input = sys.stdin.buffer.readline

def RD():
	return sys.stdin.read()

def II():
	return int(input())

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def LI():
	return list(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def TI():
	return tuple(map(int, input().split()))

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.el = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)

def main():
	(n, q) = MI()
	C = [0] + LI()
	lr = []
	for i in range(q):
		(l, r) = MI()
		lr.append([l, r, i])
	lr.sort(key=lambda x: x[1])
	R = [-1] * (n + 1)
	B = BIT(n)
	now = 1
	ans = [-1] * q
	for (l, r, i) in lr:
		while now <= r:
			if R[C[now]] != -1:
				B.add(R[C[now]], -1)
			R[C[now]] = now
			B.add(R[C[now]], 1)
			now += 1
		ans[i] = B.get(l - 1, r)
	print(*ans, sep='\n')
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
(n, q) = map(int, input().split())
C = [int(i) for i in input().split()]
LR = []
for i in range(q):
	(l, r) = map(int, input().split())
	LR.append((i, l, r))
LR.sort(key=lambda x: x[2])
LST = [0] * (n + 1)
Ans = [0] * q
n_max = 5 * 10 ** 5 + 1
nn = n_max.bit_length() + 1
BIT = [0] * 2 ** nn
BIT.insert(0, 0)

def bitsum(BIT, i):
	s = 0
	while i > 0:
		s += BIT[i]
		i -= i & -i
	return s

def bitadd(BIT, i, x):
	while i <= 2 ** nn:
		BIT[i] += x
		i += i & -i
	return BIT
cur = 0
for (i, l, r) in LR:
	while cur < r:
		if LST[C[cur]] != 0:
			bitadd(BIT, LST[C[cur]], -1)
		LST[C[cur]] = cur + 1
		bitadd(BIT, LST[C[cur]], 1)
		cur += 1
	if l == 1:
		Ans[i] = bitsum(BIT, r + 1)
	else:
		Ans[i] = bitsum(BIT, r + 1) - bitsum(BIT, l - 1)
for ans in Ans:
	print(ans)


import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

class BIT:

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.n = n

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def add(self, idx, x):
		while idx <= self.n:
			self.BIT[idx] += x
			idx += idx & -idx
		return
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
pi = [-1] * (n + 1)
ps = [[] for i in range(n)]
for i in range(n):
	l = pi[a[i]]
	if l != -1:
		ps[l].append(i)
	pi[a[i]] = i
qs = [[] for i in range(n)]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	qs[l].append((r, i))
d = BIT(n)
ans = [0] * q
for x in range(n - 1, -1, -1):
	for y in ps[x]:
		d.add(y, 1)
	for (r, i) in qs[x]:
		ans[i] = r - x + 1 - d.query(r)
print(*ans)


from operator import itemgetter
import sys

class BIT:

	def __init__(self, size: int):
		self.size = size + 1
		self.array = [0] * self.size

	def add(self, i, x):
		if not i > 0:
			return
		while i < self.size:
			self.array[i] += x
			i += i & -i

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.array[i]
			i -= i & -i
		return s

def read():
	return sys.stdin.readline().rstrip()

def main():
	(n, q) = map(int, read().split())
	c = [int(i) for i in read().split()]
	queries = [() for _ in range(q)]
	for i in range(q):
		(l, r) = map(int, read().split())
		queries[i] = (i, l, r)
	queries.sort(key=itemgetter(2))
	last = [0] * n
	bit = BIT(n)
	ans = [-1] * q
	cr = 0
	for (i, l, r) in queries:
		for ri in range(cr, r):
			ci = c[ri] - 1
			bit.add(last[ci], -1)
			last[ci] = ri + 1
			bit.add(last[ci], 1)
			cr = ri
		ans[i] = bit.sum(r) - bit.sum(l - 1)
	print(*ans, sep='\n')
main()


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)

	def add(self, i, x=1):
		i += 1
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get_sum(self, i):
		i += 1
		x = 0
		while i > 0:
			x += self.data[i]
			i -= i & -i
		return x

	def get_sum_range(self, l, r):
		return self.get_sum(r - 1) - self.get_sum(l - 1)

def main():
	(N, Q) = map(int, readline().split())
	C = list(map(int, readline().split()))
	LR = map(int, read().split())
	prev = [-1] * (N + 1)
	ps = [[] for _ in range(N)]
	for (i, c) in enumerate(C):
		if prev[c] != -1:
			ps[prev[c]].append(i)
		prev[c] = i
	qs = [[] for _ in range(N + 1)]
	for (i, (l, r)) in enumerate(zip(*[iter(LR)] * 2)):
		l -= 1
		r -= 1
		qs[l].append((r, i))
	ans = [0] * Q
	bit = BIT(N)
	for l in range(N - 1, -1, -1):
		for r in ps[l]:
			bit.add(r)
		for (r, i) in qs[l]:
			ans[i] = r - l + 1 - bit.get_sum(r)
	print(*ans, sep='\n')
	return
main()


class BIT:

	def __init__(self, N):
		self.size = N
		self.tree = [0] * (N + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(N, Q, *CLR) = map(int, open(0).read().split())
(C, LR) = (CLR[:N], CLR[N:])
memo = [-1] * (N + 1)
R = []
for (i, c) in enumerate(C):
	if memo[c] != -1:
		R.append((memo[c], i))
	memo[c] = i
R.sort(key=lambda x: x[0])
LRI = sorted(((l - 1, r - 1, i) for (i, (l, r)) in enumerate(zip(*[iter(LR)] * 2))), key=lambda x: -x[0])
bit = BIT(N + 5)
ans = [0] * Q
cur = len(R) - 1
for (l, r, i) in LRI:
	while 0 <= cur and l <= R[cur][0]:
		bit.add(R[cur][1], 1)
		cur -= 1
	ans[i] = r - l + 1 - bit.sum(r)
for a in ans:
	print(a)


import sys
from operator import itemgetter
sys.setrecursionlimit(500005)
stdin = sys.stdin
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
ns = lambda : stdin.readline().strip()
(n, q) = na()
a = na()
lasts = [-1] * (n + 1)
rs = []
for i in range(n):
	if lasts[a[i]] != -1:
		rs.append((lasts[a[i]], i))
	lasts[a[i]] = i
rs.sort(key=itemgetter(0))
qs = []
for i in range(q):
	u = na()
	qs.append((u[0] - 1, u[1] - 1, i))
qs.sort(key=itemgetter(0))

def addfenwick(ft, i, v):
	if v == 0 or i < 0:
		return
	i += 1
	while i < len(ft):
		ft[i] += v
		i += i & -i

def sumfenwick(ft, i):
	s = 0
	i += 1
	while i > 0:
		s += ft[i]
		i -= i & -i
	return s
ft = [0] * (n + 10)
anss = [0] * q
p = len(rs) - 1
for q in qs[::-1]:
	while p >= 0 and rs[p][0] >= q[0]:
		addfenwick(ft, rs[p][1], 1)
		p -= 1
	anss[q[2]] = q[1] - q[0] + 1 - sumfenwick(ft, q[1])
for v in anss:
	print(v)


import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
Q = []
for i in range(q):
	(l, r) = map(int, input().split())
	Q.append([l, r, i])
Q.sort(key=lambda x: x[1])
bit = BIT(n)
ind = [-1] * (n + 1)
ans = [0] * q
now = 0
for (l, r, num) in Q:
	while now < r:
		x = c[now]
		if ind[x] == -1:
			ind[x] = now
			bit.add(now, 1)
		else:
			bit.add(ind[x], -1)
			ind[x] = now
			bit.add(now, 1)
		now += 1
	ans[num] = bit.sum(r) - bit.sum(l - 1)
for i in ans:
	print(i)


(n, q) = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1] * (n + 1)
A = [0] * q
U = 10 ** 6
LR = tuple((tuple(map(int, input().split())) for _ in range(q)))
W = sorted((r * U + i for (i, (l, r)) in enumerate(LR)))
B = [0] * (1 << n.bit_length())

def add(i, a):
	while i <= n:
		B[i] += a
		i += i & -i

def acc(i):
	res = 0
	while i:
		res += B[i]
		i -= i & -i
	return res
temp = 1
for w in W:
	(r, i) = divmod(w, U)
	while temp <= r:
		c = C[temp]
		add(temp, 1)
		if D[c] != -1:
			add(D[c], -1)
		D[c] = temp
		temp += 1
	l = LR[i][0]
	A[i] = acc(r) - acc(l - 1)
print(*A, sep='\n')


from bisect import *
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
c = list(map(int, input().split()))

class BIT:

	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += i & -i
query = [list(map(int, input().split())) + [i] for i in range(q)]
query.sort(key=lambda x: x[1])
appear = [-1] * (n + 2)
bit = BIT(n)
right = 0
ans = [None] * q
for (l, r, z) in query:
	for i in range(right, r):
		num = appear[c[i]]
		if num != -1:
			bit.add(num + 1, -1)
		appear[c[i]] = i
		bit.add(i + 1, 1)
	right = r
	ans[z] = bit.sum(r) - bit.sum(l - 1)
print(*ans, sep='\n')


class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(N, Q) = map(int, input().split())
c = list(map(int, input().split()))
q = []
for k in range(Q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	q.append([l, r, k])
q.sort(key=lambda x: x[1])
ans = [0 for k in range(Q)]
good = BIT(N)
lastapp = [-1 for _ in range(N)]
end = -1
for k in range(Q):
	l = q[k][0]
	r = q[k][1]
	a = q[k][2]
	for j in range(r, end, -1):
		if lastapp[c[j] - 1] == -1:
			lastapp[c[j] - 1] = j
			good.add(j + 1, 1)
		elif lastapp[c[j] - 1] < j:
			good.add(lastapp[c[j] - 1] + 1, -1)
			good.add(j + 1, 1)
			lastapp[c[j] - 1] = j
	ans[a] = good.sum(r + 1) - good.sum(l)
	end = r
for k in range(Q):
	print(ans[k])


class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)
		self.el = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.bit[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i - 1)

	def lower_bound(self, x):
		w = i = 0
		k = 1 << self.n.bit_length()
		while k:
			if i + k <= self.n and w + self.bit[i + k] < x:
				w += self.bit[i + k]
				i += k
			k >>= 1
		return i + 1

def solve():
	(N, Q) = map(int, input().split())
	C = list(map(int, input().split()))
	lis = [-1] * (N + 1)
	bit = BIT(N)
	ans = [0] * Q
	A = [list(map(int, input().split())) + [i] for i in range(Q)]
	A.sort(key=lambda x: x[1])
	now = 0
	for (l, r, ind) in A:
		for i in range(now, r):
			if lis[C[i]] >= 0:
				bit.add(lis[C[i]] + 1, -1)
			lis[C[i]] = i
			bit.add(i + 1, 1)
		ans[ind] = bit.get(l, r)
		now = r
	return ans
print(*solve(), sep='\n')


import sys
read = sys.stdin.buffer.readline

class BIT:

	def __init__(self, N):
		self.N = N
		self.bit = [0] * N

	def add(self, a, w):
		x = a
		while x < self.N:
			self.bit[x] += w
			x |= x + 1

	def get(self, a):
		(ret, x) = (0, a - 1)
		while x >= 0:
			ret += self.bit[x]
			x = (x & x + 1) - 1
		return ret

	def cum(self, l, r):
		return self.get(r) - self.get(l)

def update(x, i):
	if good[x] == -1:
		good[x] = i
		bit.add(i, 1)
	else:
		bit.add(good[x], -1)
		good[x] = i
		bit.add(good[x], 1)
	return
(N, Q) = map(int, read().split())
c = tuple(map(int, read().split()))
Query = []
for i in range(Q):
	(l, r) = map(lambda x: int(x) - 1, read().split())
	Query.append((l, r, i))
Query.sort(key=lambda x: x[1])
ans = [-1] * Q
good = [-1] * (N + 1)
bit = BIT(N)
i = 0
for (L, R, w) in Query:
	while i <= R:
		update(c[i], i)
		i += 1
	ans[w] = bit.cum(L, R + 1)
print(*ans, sep='\n')


import sys
input = sys.stdin.readline

def solve():

	def makeBIT(numEle):
		numPow2 = 2 ** (numEle - 1).bit_length()
		data = [0] * (numPow2 + 1)
		return (data, numPow2)

	def addValue(iA, A):
		iB = iA + 1
		while iB <= numPow2:
			data[iB] += A
			iB += iB & -iB

	def getSum(iA):
		iB = iA + 1
		ans = 0
		while iB > 0:
			ans += data[iB]
			iB -= iB & -iB
		return ans

	def getRangeSum(iFr, iTo):
		return getSum(iTo) - getSum(iFr - 1)
	(N, Q) = map(int, input().split())
	cs = list(map(lambda x: int(x) - 1, input().split()))
	LRs = []
	Lss = [[] for _ in range(N)]
	for i in range(Q):
		(L, R) = map(int, input().split())
		(L, R) = (L - 1, R - 1)
		LRs.append((L, R))
		Lss[R].append((L, i))
	(data, numPow2) = makeBIT(Q)
	anss = [0] * Q
	posRights = [-1] * N
	for (R, c) in enumerate(cs):
		if posRights[c] != -1:
			addValue(posRights[c], -1)
		addValue(R, 1)
		posRights[c] = R
		for (L, i) in Lss[R]:
			anss[i] = getRangeSum(L, R)
	print('\n'.join(map(str, anss)))
solve()


def bitadd(a, w, bit):
	x = a
	while x <= len(bit) - 1:
		bit[x] += w
		x += x & -1 * x

def bitsum(a, bit):
	ret = 0
	x = a
	while x > 0:
		ret += bit[x]
		x -= x & -1 * x
	return ret
from sys import stdin
(N, Q) = map(int, stdin.readline().split())
c = list(map(int, stdin.readline().split()))
last = [1] * (N + 1)
li = [[] for i in range(N + 2)]
ans = [None] * Q
for i in range(Q):
	(L, R) = map(int, stdin.readline().split())
	L += 1
	R += 1
	li[R].append((L, i))
BIT = [0] * (N + 2)
bitadd(1, N, BIT)
for i in range(N):
	nc = c[i]
	lastind = last[nc]
	last[nc] = i + 2
	bitadd(lastind, -1, BIT)
	bitadd(i + 2, 1, BIT)
	for (l, qind) in li[i + 2]:
		ans[qind] = bitsum(i + 2, BIT) - bitsum(l - 1, BIT)
print(*ans)


NN = 19
BIT = [0] * (2 ** NN + 1)

def addbit(i, x=1):
	while i <= 2 ** NN:
		BIT[i] += x
		i += i & -i

def getsum(i):
	ret = 0
	while i != 0:
		ret += BIT[i]
		i -= i & -i
	return ret
(N, Q) = map(int, input().split())
C = [int(a) - 1 for a in input().split()]
X = [[] for _ in range(N)]
for i in range(Q):
	(l, r) = map(int, input().split())
	X[r - 1].append((l - 1, i))
last = [-1] * N
ANS = [-1] * Q
addbit(1, N)
for r in range(N):
	c = C[r]
	addbit(last[c] + 2, -1)
	addbit(r + 2)
	last[c] = r
	for (l, i) in X[r]:
		ANS[i] = getsum(1 << NN) - getsum(l + 1)
print(*ANS, sep='\n')


import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, n):
		self.array = [0] * (n + 1)
		self.size = n

	def sum(self, i):
		s = 0
		tmp = i
		while tmp > 0:
			s += self.array[tmp]
			tmp -= tmp & -tmp
		return s

	def add(self, i, x):
		tmp = i + 1
		while tmp <= self.size:
			self.array[tmp] += x
			tmp += tmp & -tmp
(n, q) = map(int, input().split())
(*C,) = map(lambda x: int(x) - 1, input().split())
P = [0] * n
N = [None] * n
for i in range(n)[::-1]:
	if P[C[i]]:
		N[i] = P[C[i]]
	P[C[i]] = i
F = [0] * n
B = BIT(n)
for i in range(n):
	if F[C[i]] == 0:
		B.add(i, 1)
		F[C[i]] = 1
XY = [tuple(map(int, input().split())) for j in range(q)]
ids = list(range(q))
ids.sort(key=lambda j: XY[j][0])
a = 0
lst = [0] * q
for j in ids:
	(x, y) = XY[j]
	for i in range(a, x - 1):
		if N[i]:
			B.add(N[i], 1)
	a = x - 1
	lst[j] = B.sum(y) - B.sum(x - 1)
print(*lst, sep='\n')


import sys
input = sys.stdin.buffer.readline
(n, Q) = map(int, input().split())
c = [0] + list(map(int, input().split()))
dg = 10 ** 6
dg2 = 10 ** 12
res = [0] * Q
LRI = []
for i in range(Q):
	(l, r) = map(int, input().split())
	LRI.append(l * dg2 + r * dg + i)
LRI.sort()
BIT = [0] * (n + 1)

def BIT_query(idx):
	res_sum = 0
	while idx > 0:
		res_sum += BIT[idx]
		idx -= idx & -idx
	return res_sum

def BIT_update(idx, x):
	while idx <= n:
		BIT[idx] += x
		idx += idx & -idx
	return
fi = [[] for i in range(n + 1)]
nxt = [-1] * (n + 1)
for i in range(1, n + 1):
	num = c[i]
	if len(fi[num]) == 0:
		BIT_update(i, 1)
	else:
		nxt[fi[num][-1]] = i
	fi[num].append(i)
idx = 0
for i in range(1, n + 1):
	while idx < Q:
		(l, ri) = divmod(LRI[idx], dg2)
		if l != i:
			break
		(r, resi) = divmod(ri, dg)
		res[resi] = BIT_query(r)
		idx += 1
	BIT_update(i, -1)
	if nxt[i] != -1:
		BIT_update(nxt[i], 1)
print(*res, sep='\n')


class BIT:

	def __init__(self, size):
		self.array = [0] * size
		self.size = size

	def add(self, ind, value):
		while ind <= self.size:
			self.array[ind - 1] += value
			ind += ind & -ind

	def sum(self, x):
		out = 0
		while x > 0:
			out += self.array[x - 1]
			x -= x & -x
		return out
import sys
input = sys.stdin.readline

def main(N, Q, c, q):
	bit = BIT(N)
	rbi = {}
	ans = [0] * Q
	q.sort(key=lambda x: x[1])
	R = 0
	for (l, r, ind) in q:
		for i in range(R, r):
			if c[i] in rbi:
				bit.add(rbi[c[i]], -1)
			rbi[c[i]] = i + 1
			bit.add(rbi[c[i]], 1)
		ans[ind] = bit.sum(r) - bit.sum(l - 1)
		R = r
	return ans
(N, Q) = map(int, input().split())
c = list(map(int, input().split()))
q = list((list(map(int, input().split())) + [i] for i in range(Q)))
ans = main(N, Q, c, q)
for i in ans:
	print(i)


class BinaryIndexedTree:

	def __init__(self, N):
		self.N = N
		self.arr = [0] * (N + 1)

	def query(self, i):
		ret = 0
		i += 1
		while i:
			ret += self.arr[i]
			lsb = i & -i
			i -= lsb
		return ret

	def add(self, i, v):
		i += 1
		while i < self.N + 1:
			lsb = i & -i
			self.arr[i] += v
			i += lsb

def main():
	(N, Q) = map(int, input().split())
	C = list(map(int, input().split()))
	queries = [None] * Q
	for i in range(Q):
		(l, r) = map(int, input().split())
		queries[i] = [l, r, i]
	queries.sort(key=lambda x: x[1])
	bit = BinaryIndexedTree(N)
	numdupls = 0
	prevs = [-1] * N
	cur = 0
	ans = [-999] * Q
	for i in range(Q):
		(l, r, qindex) = queries[i]
		while cur < r:
			c = C[cur] - 1
			if prevs[c] != -1:
				bit.add(prevs[c], 1)
				numdupls += 1
			prevs[c] = cur
			cur += 1
		ans[qindex] = r - l + 1 - (numdupls - bit.query(l - 2))
	for i in range(Q):
		print(ans[i])
main()


def position_zip(a, flag):
	j = 0
	d = {}
	for i in sorted(a):
		if i in d:
			continue
		d[i] = j
		j += 1
	if flag == 1:
		return d
	return [d[i] for i in a]

class BinaryIndexedTree:

	def __init__(self, n):
		self.bit = [0] * n

	def add(self, i, x):
		i += 1
		while i <= len(self.bit):
			self.bit[i - 1] += x
			i += i & -i

	def sum_sub(self, i):
		a = 0
		i += 1
		while i:
			a += self.bit[i - 1]
			i -= i & -i
		return a

	def sum(self, i, j):
		a = self.sum_sub(j + 1)
		if i != 0:
			a -= self.sum_sub(i - 1)
		return a
xx = 1 << 20
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
a = position_zip(a, 0)
k = max(a) + 1
ans = [0] * q
queries = []
for i in range(q):
	(l, r) = list(map(int, input().split()))
	l -= 1
	r -= 1
	queries.append(r << 40 | l << 20 | i)
queries.sort()
for i in range(q):
	ind = queries[i] % xx
	queries[i] >>= 20
	l = queries[i] % xx
	queries[i] >>= 20
	r = queries[i]
	queries[i] = (r, l, ind)
queries.append((10 * 20, 0, 0))
lastAppeared = [-1] * k
bitt = BinaryIndexedTree(n)
j = 0
for i in range(n):
	if lastAppeared[a[i]] != -1:
		bitt.add(lastAppeared[a[i]], -1)
		bitt.add(i, 1)
		lastAppeared[a[i]] = i
	else:
		bitt.add(i, 1)
		lastAppeared[a[i]] = i
	while queries[j][0] == i:
		(r, l, ind) = queries[j]
		j += 1
		ans[ind] = bitt.sum(l, r - 1)
print(*ans)


class BIT:

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.num = n

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		while idx <= self.num:
			self.BIT[idx] += x
			idx += idx & -idx
		return
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
c = list(map(int, input().split()))
query = []
for i in range(Q):
	(l, r) = map(int, input().split())
	query.append((l, r, i))
query.sort(key=lambda x: -x[1])
ans = [0] * Q
last = [0 for i in range(N)]
B = BIT(N)
for i in range(N):
	val = c[i] - 1
	if last[val] != 0:
		B.update(last[val], -1)
	last[val] = i + 1
	B.update(i + 1, 1)
	while query and query[-1][1] == i + 1:
		(l, r, id) = query.pop()
		res = B.query(r) - B.query(l - 1)
		ans[id] = res
for i in range(Q):
	print(ans[i])


class FenwickTree:

	def __init__(self, size):
		self.size = size
		self.array = [0] * size

	def add(self, index, value):
		while index < self.size:
			self.array[index] += value
			index += index & -index

	def sum(self, index):
		answer = 0
		while index > 0:
			answer += self.array[index]
			index -= index & -index
		return answer

	def rangesum(self, start, end):
		return self.sum(end) - self.sum(start - 1)

def solve():
	(N, Q) = map(int, input().split())
	(*c,) = map(int, input().split())
	tree2 = FenwickTree(N + 1)
	m = [list(map(int, input().split())) for _ in range(Q)]
	idxs = sorted(list(range(Q)), key=lambda i: m[i][1])
	right = 0
	pos = [-1] * (N + 1)
	ans = [-1] * Q
	for idx in idxs:
		(l, r) = m[idx]
		for i in range(right, r):
			x = pos[c[i]]
			if x != -1:
				tree2.add(x, -1)
			pos[c[i]] = i + 1
			tree2.add(i + 1, 1)
		ans[idx] = tree2.rangesum(l, r)
		right = r
	print(*ans, sep='\n')
solve()


def bit_add(arr, n, i, x):
	while i <= n:
		arr[i] += x
		i += i & -i

def bit_sum(arr, i):
	result = 0
	while i > 0:
		result += arr[i]
		i ^= i & -i
	return result
(n, q) = map(int, input().split())
color = [int(i) for i in input().split()]
query = []
rli = [0] * q
for i in range(q):
	(l, r) = map(int, input().split())
	query.append((l, r))
	rli[i] = (r << 40) + (l << 20) + i
rli.sort()
mask = (1 << 20) - 1
bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0
for j in range(q):
	k = rli[j]
	r = k >> 40
	l = k >> 20 & mask
	i = k & mask
	while p < r:
		c = color[p]
		before_appeared = appeared[c]
		if before_appeared != -1:
			bit_add(bit, bn, before_appeared + 2, -1)
		bit_add(bit, bn, p + 2, 1)
		appeared[c] = p
		p += 1
	ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)
print('\n'.join(map(str, ans)))


def main():
	import sys
	input = sys.stdin.readline

	class BIT:

		def __init__(self, n):
			self.tree = [0] * (n + 1)
			self.size = n

		def add(self, i, x):
			while i <= self.size:
				self.tree[i] += x
				i += i & -i

		def sum(self, i):
			s = 0
			while i > 0:
				s += self.tree[i]
				i -= i & -i
			return s
	(N, Q) = map(int, input().split())
	bit = BIT(N)
	C = list(map(int, input().split()))
	query = []
	for i in range(Q):
		(l, r) = map(int, input().split())
		query.append([l, r, i])
	query.sort(key=lambda x: x[1])
	ans = [0] * Q
	colorMemo = [0] * (N + 1)
	cur = 1
	for q in query:
		(l, r, j) = q
		for i in range(cur, r + 1):
			c = C[i - 1]
			if colorMemo[c]:
				bit.add(colorMemo[c], -1)
			bit.add(i, 1)
			colorMemo[c] = i
		cur = r + 1
		ans[j] = bit.sum(r) - bit.sum(l - 1)
	print(*ans, sep='\n')
main()


import sys
input = sys.stdin.buffer.readline
(N, Q) = map(int, input().split())
Color = [0] + list(map(int, input().split()))
Query = []
for i in range(Q):
	(l, r) = map(int, input().split())
	Query.append(r * 10 ** 12 + l * 10 ** 6 + i)
Query.sort()
Ans = [0] * Q
BIT = [0] * (N + 1)

def BIT_query(idx):
	res_sum = 0
	while idx > 0:
		res_sum += BIT[idx]
		idx -= idx & -idx
	return res_sum

def BIT_update(idx, x):
	while idx <= N:
		BIT[idx] += x
		idx += idx & -idx
	return
cn = max(Color)
Last = [-1] * cn
cnt = 0
for q in Query:
	r = q // 10 ** 12
	l = q % 10 ** 12 // 10 ** 6
	i = q % 10 ** 6
	while cnt < r:
		cnt += 1
		c = Color[cnt] - 1
		if Last[c] == -1:
			Last[c] = cnt
			BIT_update(cnt, 1)
		else:
			x = Last[c]
			BIT_update(x, -1)
			Last[c] = cnt
			BIT_update(cnt, 1)
	Ans[i] = BIT_query(r) - BIT_query(l - 1)
for a in Ans:
	print(a)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
	(l, r) = map(int, input().split())
	query.append((i, l - 1, r - 1))

class BinaryIndexedTree:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * n

	def add(self, i, w):
		x = i + 1
		while x <= self.n:
			self.bit[x - 1] += w
			x += x & -x

	def sum(self, i):
		ret = 0
		x = i + 1
		while x > 0:
			ret += self.bit[x - 1]
			x -= x & -x
		return ret
bit = BinaryIndexedTree(n + 1)
query.sort(key=lambda x: x[2])
last = [None] * n
ans = [None] * q
nr = -1
for (idx, l, r) in query:
	for cr in range(nr + 1, r + 1):
		if last[c[cr]] is not None:
			bit.add(last[c[cr]] + 1, -1)
		last[c[cr]] = cr
		bit.add(cr + 1, 1)
	nr = r
	ans[idx] = bit.sum(r + 1) - bit.sum(l)
for i in ans:
	print(i)


import sys
input = sys.stdin.readline

def main():
	(n, q) = map(int, input().split())
	c = list(map(int, input().split()))
	lri = [list(map(int, input().split())) + [i] for i in range(q)]
	lri.sort(key=lambda x: x[1])

	class BIT:

		def __init__(self, n):
			self.n = n
			self.data = [0] * (n + 1)
			self.el = [0] * (n + 1)

		def sum(self, i):
			s = 0
			while i > 0:
				s += self.data[i]
				i -= i & -i
			return s

		def add(self, i, x):
			self.el[i] += x
			while i <= self.n:
				self.data[i] += x
				i += i & -i

		def get(self, i, j=None):
			if j is None:
				return self.el[i]
			return self.sum(j) - self.sum(i)
	bt = BIT(n + 1)
	dc = {}
	ans = [0] * q
	j = 0
	for i in range(n):
		x = c[i]
		if x in dc:
			bt.add(dc[x], -1)
		bt.add(i + 1, 1)
		dc[x] = i + 1
		while j < q and i + 1 == lri[j][1]:
			(l, r, k) = lri[j]
			ans[k] = bt.get(l - 1, r)
			j += 1
		if j == q:
			break
	print(*ans, sep='\n')
main()


class BIT:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * (n + 1)

	def update(self, i, v):
		while i <= self.n:
			self.tree[i] += v
			i += i & -i

	def query(self, i):
		v = 0
		while i:
			v += self.tree[i]
			i -= i & -i
		return v
(N, Q) = map(int, input().split())
(*c,) = map(int, input().split())
q = [[] for _ in range(N + 1)]
for i in range(Q):
	(x, y) = map(int, input().split())
	q[y - 1].append([i, x - 1])
bit = BIT(N)
finds = [-1] * (N + 1)
ans = [0] * Q
for i in range(N):
	if finds[c[i]] != -1:
		bit.update(finds[c[i]] + 1, -1)
	finds[c[i]] = i
	bit.update(finds[c[i]] + 1, 1)
	for (j, x) in q[i]:
		ans[j] = bit.query(i + 1) - bit.query(x)
for a in ans:
	print(a)


import sys
input = sys.stdin.buffer.readline
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
l = [0] * q
r = [0] * q
queries = [[] for _ in range(n)]
rights = [[] for _ in range(n)]
for i in range(q):
	(l[i], r[i]) = map(int, input().split())
	l[i] -= 1
	queries[l[i]].append(i)
last_app = [-1] * (n + 1)
for i in range(n):
	if last_app[c[i]] != -1:
		last = last_app[c[i]]
		rights[last].append(i)
	last_app[c[i]] = i
ans = [0] * q
seg = [0] * (1 << 20)

def add(x):
	x += 1 << 19
	while x:
		seg[x] += 1
		x = x // 2

def sum_of(l, r):
	l += 1 << 19
	r += 1 << 19
	ans = 0
	while l < r:
		if l % 2 == 1:
			ans += seg[l]
			l += 1
		if r % 2 == 1:
			ans += seg[r - 1]
			r -= 1
		l //= 2
		r //= 2
	return ans
for i in range(n - 1, -1, -1):
	for right in rights[i]:
		add(right)
	for q_ind in queries[i]:
		left = l[q_ind]
		right = r[q_ind]
		ans[q_ind] = right - left - sum_of(left, right)
for i in range(q):
	print(ans[i])


from sys import stdin
input = stdin.readline

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(N, Q) = map(int, input().split())
c = list(map(int, input().split()))
lr = []
for i in range(Q):
	(l, r) = map(int, input().split())
	lr.append([l, r, i])
lr.sort(key=lambda x: x[1])
rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q
for i in range(N):
	if rightest[c[i]] != -1:
		bit.add(rightest[c[i]] + 1, -1)
	rightest[c[i]] = i
	bit.add(i + 1, 1)
	while current_q < Q and lr[current_q][1] == i + 1:
		ans[lr[current_q][2]] = bit.sum(lr[current_q][1]) - bit.sum(lr[current_q][0] - 1)
		current_q += 1
for i in range(Q):
	print(ans[i])


def A(i, x):
	while i <= n:
		t[i] += x
		i += i & -i
(n, q, *c) = map(int, open(0).read().split())
a = [0] * q
(j, *b) = t = [0] * 9 ** 6
for i in sorted(range(q), key=lambda x: c[x + x - ~n]):
	while j < c[i + i - ~n]:
		d = c[j]
		j += 1
		A(b[d] + 1, 1)
		b[d] = j
		A(j + 1, -1)
	l = c[i + i + n]
	while l:
		a[i] += t[l]
		l -= l & -l
print(*a)


SHIFT = 1 << 20

def main():
	(N, Q) = (int(i) for i in input().split())
	C = [int(i) for i in input().split()]
	Query = []
	for j in range(Q):
		(le, ri) = (int(i) for i in input().split())
		Query.append(ri << 40 | le << 20 | j)
	Query.sort()
	for i in range(Q):
		j = Query[i] % SHIFT
		Query[i] >>= 20
		le = Query[i] % SHIFT
		Query[i] >>= 20
		ri = Query[i]
		Query[i] = (le, ri, j)
	Query.append((-1, -1, -1))

	def sum(tree, i):
		s = 0
		while i > 0:
			s += tree[i]
			i -= i & -i
		return s

	def add(tree, i, x):
		while i <= N:
			tree[i] += x
			i += i & -i
	lastappend = [-1] * (N + 1)
	bit = [0] * (N + 1)
	idx = 0
	ans = [0] * Q
	for (i, a) in enumerate(C, start=1):
		if lastappend[a] != -1:
			add(bit, lastappend[a], -1)
		lastappend[a] = i
		add(bit, i, 1)
		while i == Query[idx][1]:
			(le, ri, j) = Query[idx]
			ans[j] = sum(bit, ri) - sum(bit, le - 1)
			idx += 1
	print(*ans, sep='\n')
main()


(n, q) = map(int, input().split())
bit = [0] * (n + 1)

def fenwick_add(x, w):
	while x <= n:
		bit[x] += w
		x += x & -x

def fenwick_sum(x):
	sm = 0
	while x > 0:
		sm += bit[x]
		x -= x & -x
	return sm
c = list(map(int, input().split()))
p = [-1] * (n + 1)
ps = [[] for _ in range(n + 1)]
for (i, v) in enumerate(c):
	l = p[v]
	if l != -1:
		ps[l].append(i)
	p[v] = i
qs = [[] for _ in range(n + 1)]
for i in range(q):
	(l, r) = map(int, input().split())
	qs[l - 1].append([r - 1, i])
ans = [0] * q
for i in range(n - 1, -1, -1):
	for v in ps[i]:
		fenwick_add(v, 1)
	for v in qs[i]:
		(r, qi) = v
		ans[qi] = r - i + 1 - fenwick_sum(r)
print(*ans, sep='\n')


import sys

def input():
	return sys.stdin.readline().strip()

def mapint():
	return map(int, input().split())
sys.setrecursionlimit(10 ** 9)
(N, Q) = mapint()
Cs = list(mapint())
LR = []
for i in range(Q):
	(l, r) = mapint()
	LR.append((l, r, i))
LR.sort(key=lambda x: x[1])
A = [0] * N

def add(A, a, w):
	x = a
	while x <= N:
		A[x - 1] += w
		x += x & -x

def sums(A, a):
	x = a
	S = 0
	while x != 0:
		S += A[x - 1]
		x -= x & -x
	return S
ans = [0] * Q
idx = 0
dic = {}
for i in range(N):
	c = Cs[i]
	if c not in dic:
		dic[c] = i + 1
		add(A, i + 1, 1)
	else:
		past = dic[c]
		dic[c] = i + 1
		add(A, past, -1)
		add(A, i + 1, 1)
	while idx < Q and LR[idx][1] <= i + 1:
		(l, r, ans_idx) = LR[idx]
		ans[ans_idx] = sums(A, r) - sums(A, l - 1)
		idx += 1
for a in ans:
	print(a)


(N, Q) = map(int, input().split())
C = [int(i) for i in input().split()]
pi = [-1] * (N + 1)
ps = [[] for _ in range(N + 1)]
for i in range(N):
	l = pi[C[i]]
	if l != -1:
		ps[l].append(i)
	pi[C[i]] = i
qs = [[] for _ in range(N + 1)]
for i in range(Q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	qs[l].append((r, i))
bit = [0] * (N + 1)

def bit_sum(idx):
	res_sum = 0
	while idx > 0:
		res_sum += bit[idx]
		idx -= idx & -idx
	return res_sum

def bit_add(idx, x):
	while idx <= N:
		bit[idx] += x
		idx += idx & -idx
	return True
ans = [0] * Q
for x in range(N - 1, -1, -1):
	for y in ps[x]:
		bit_add(y, 1)
	for (r, i) in qs[x]:
		ans[i] = r - x + 1 - bit_sum(r)
for i in range(Q):
	print(ans[i])


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
	(l, r) = map(lambda x: int(x) - 1, input().split())
	query.append(l << 40 | r << 20 | i)
query.sort()
ball = [list() for i in range(n)]
for (i, x) in enumerate(c):
	ball[x].append(i)
bit = [0] * (n + 1)

def add(i, x):
	i += 1
	while i <= n:
		bit[i] += x
		i += i & -i

def get(i):
	i += 1
	s = 0
	while i:
		s += bit[i]
		i -= i & -i
	return s
for i in ball:
	if i:
		add(i[0], 1)
		i.reverse()
at = 0
ans = [0] * q
for x in query:
	l = x >> 40
	r = x >> 20 & 1048575
	i = x & 1048575
	while at < l:
		b = ball[c[at]]
		add(b[-1], -1)
		b.pop()
		if b:
			add(b[-1], 1)
		at += 1
	ans[i] = get(r) - get(l - 1)
for i in ans:
	print(i)


(n, q) = map(int, input().split())
N = n
data = [0] * (N + 1)

def add(k, x):
	while k <= N:
		data[k] += x
		k += k & -k

def get(k):
	s = 0
	while k:
		s += data[k]
		k -= k & -k
	return s
c = [int(i) for i in input().split()]
Q = []
for i in range(q):
	(l, r) = map(int, input().split())
	Q.append((l, r, i))
Ans = [0 for i in range(q)]
F = [-1 for i in range(5 * 10 ** 5 + 1)]
Q.sort(key=lambda x: x[1])
for i in range(n):
	add(i + 1, 1)
i = 0
for nowQ in Q:
	while nowQ[1] != i:
		ci = c[i]
		if F[ci] >= 0:
			add(F[ci] + 1, -1)
		F[ci] = i
		i += 1
	Ans[nowQ[2]] = -get(nowQ[0] - 1) + get(nowQ[1])
print('\n'.join([str(i) for i in Ans]))


import sys
from operator import itemgetter

def input():
	return sys.stdin.readline().rstrip()

class BinaryIndexedTree:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def query(self, l, r):
		return self.sum(r) - self.sum(l)
(n, q) = (int(x) for x in input().split())
C = list((int(x) - 1 for x in input().split()))
LR = [tuple((int(x) for x in input().split())) for _ in range(q)]
bit = BinaryIndexedTree(n)
color_right_index = [-1] * n
queries = [(i, l - 1, r - 1) for (i, (l, r)) in enumerate(LR)]
queries.sort(key=itemgetter(2))
ANS = [0] * q
k = 0
for (i, l, r) in queries:
	while k <= r and k <= n:
		color = C[k]
		if color_right_index[color] != -1:
			bit.add(color_right_index[color], -1)
		color_right_index[C[k]] = k
		bit.add(k, 1)
		k += 1
	ANS[i] = bit.query(l, r + 1)
for ans in ANS:
	print(ans)


from sys import stdin

class BIT:

	def __init__(self, n):
		self.data = [0] * (n + 10)

	def upd(self, pos, val=1):
		pos += 1
		while pos < len(self.data):
			self.data[pos] += val
			pos += pos & -pos

	def get(self, pos):
		ans = 0
		pos += 1
		while pos > 0:
			ans += self.data[pos]
			pos -= pos & -pos
		return ans

	def get_range(self, l, r):
		return self.get(r) - self.get(l - 1)

def main():
	(n, q) = map(int, stdin.readline().split())
	color = list(map(int, stdin.readline().split()))
	queries = []
	for i in range(q):
		(l, r) = map(int, stdin.readline().split())
		queries.append((l, r, i))
	queries.sort(key=lambda val: val[1])
	ans = [0] * q
	prev_pos = [0] * (n + 1)
	bit = BIT(n + 1)
	f = 0
	for (cur_pos, color) in enumerate(color, 1):
		bit.upd(prev_pos[color], -1)
		bit.upd(cur_pos, 1)
		prev_pos[color] = cur_pos
		while f < q and queries[f][1] == cur_pos:
			ans[queries[f][2]] = bit.get_range(queries[f][0], queries[f][1])
			f += 1
	print('\n'.join(map(str, ans)))
main()


import sys

def bit_add(arr, n, i, x):
	while i <= n:
		arr[i] += x
		i += i & -i

def bit_sum(arr, i):
	result = 0
	while i > 0:
		result += arr[i]
		i ^= i & -i
	return result
(n, q) = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
mp = map(int, sys.stdin.buffer.read().split())
itr = zip(mp, mp)
rli = [0] * q
for i in range(q):
	(l, r) = next(itr)
	rli[i] = (r << 40) + (l << 20) + i
rli.sort()
mask = (1 << 20) - 1
bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0
for j in range(q):
	k = rli[j]
	r = k >> 40
	l = k >> 20 & mask
	i = k & mask
	while p < r:
		c = ccc[p]
		before_appeared = appeared[c]
		if before_appeared != -1:
			bit_add(bit, bn, before_appeared + 2, -1)
		bit_add(bit, bn, p + 2, 1)
		appeared[c] = p
		p += 1
	ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)
print('\n'.join(map(str, ans)))


def solve():
	import sys
	input = sys.stdin.readline

	class BIT:

		def __init__(self, n):
			self.n = n
			self.data = [0] * n

		def sum(self, i):
			s = 0
			while i > 0:
				s += self.data[i - 1]
				i &= i - 1
			return s

		def update(self, i, x):
			while i < self.n:
				self.data[i] += x
				i |= i + 1
	(n, q) = map(int, input().split())
	c = list(map(int, input().split()))
	odr_r = [[] for _ in range(n + 1)]
	for i in range(q):
		(l, r) = map(int, input().split())
		odr_r[r].append((l - 1, i))
	b = BIT(n)
	diff = 0
	ans = [-1] * q
	last = [-1] * (n + 1)
	for (i, v) in enumerate(c):
		if last[v] != -1:
			b.update(last[v], -1)
		else:
			diff += 1
		b.update(i, 1)
		last[v] = i
		for (l, j) in odr_r[i + 1]:
			ans[j] = diff - b.sum(l)
	print('\n'.join(map(str, ans)))
	return
solve()


class BIT:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * (n + 1)

	def sum(self, x):
		sum = 0
		while x > 0:
			sum += self.tree[x]
			x -= x & -x
		return sum

	def update(self, x, k):
		while x <= self.n:
			self.tree[x] += k
			x += x & -x

	def build(self, a):
		for i in range(len(a)):
			k = a[i]
			x = i + 1
			while x <= self.n:
				self.tree[x] += k
				x += x & -x

class Query:

	def __init__(self, r, l, idx):
		self.l = l
		self.r = r
		self.idx = idx

def solve(case):
	(n, q) = map(int, input().split())
	c = list(map(int, input().split()))
	query = []
	for i in range(q):
		(l, r) = map(int, input().split())
		query.append(Query(r, l, i))
	query.sort(key=lambda x: x.r)
	bit = BIT(n)
	lastvis = [-1] * (n + 1)
	ind = 0
	ans = [0] * q
	for i in range(n):
		if lastvis[c[i]] != -1:
			bit.update(lastvis[c[i]] + 1, -1)
		lastvis[c[i]] = i
		bit.update(i + 1, 1)
		while ind < q and query[ind].r == i + 1:
			ans[query[ind].idx] = bit.sum(i + 1) - bit.sum(query[ind].l - 1)
			ind += 1
	for i in range(q):
		print(ans[i])
solve(1)


import sys

def main():
	(n, q, *c) = map(int, sys.stdin.buffer.read().split())
	a = [0] * q
	(j, *b) = t = [0] * 9 ** 6
	for i in sorted(range(q), key=lambda x: c[x + x - ~n]):
		(l, r) = (c[i + i + n], c[i + i - ~n])
		while j < r:
			k = c[j]
			j += 1
			(x, y, b[k]) = (b[k] + 1, j + 1, j)
			while x <= n:
				t[x] += 1
				x = x + (x & -x)
			while y <= n:
				t[y] -= 1
				y = y + (y & -y)
		s = 0
		while l:
			s = s + t[l]
			l = l - (l & -l)
		a[i] = s
	print(' '.join(map(str, a)))
main()


from sys import stdin
input = stdin.readline
from collections import defaultdict

class BIT:

	def __init__(self, N):
		self.N = N
		self.arr = [0] * (N + 1)

	def add(self, ind, x=1):
		ind += 1
		while ind <= self.N:
			self.arr[ind] += x
			ind += ind & -ind

	def get_sum(self, ind):
		ind += 1
		res = 0
		while ind > 0:
			res += self.arr[ind]
			ind -= ind & -ind
		return res

def solve():
	(N, Q) = map(int, input().split())
	c = list(map(int, input().split()))
	query = [tuple(map(int, inp.split())) for inp in stdin.read().splitlines()]
	prev = [-1] * (N + 1)
	nxt = [-1] * (N + 1)
	for (i, v) in enumerate(c):
		if prev[v] != -1:
			nxt[prev[v]] = i
		prev[v] = i
	q = defaultdict(list)
	for (i, (l, r)) in enumerate(query):
		q[l - 1].append((r - 1, i))
	bit = BIT(N)
	ans = [0] * Q
	for l in range(N - 1, -1, -1):
		if nxt[l] != -1:
			bit.add(nxt[l], 1)
		for (r, i) in q[l]:
			ans[i] = r - l + 1 - bit.get_sum(r)
	for a in ans:
		print(a)
solve()


from operator import add, mul, sub, or_

class BIT:

	def __init__(self, n, op, ie):
		self.n = n
		self.tree = [ie] * (n + 1)
		self.op = op
		self.ie = ie

	def update(self, i, v):
		while i <= self.n:
			self.tree[i] = self.op(self.tree[i], v)
			i += i & -i

	def query(self, i):
		v = self.ie
		while i:
			v = self.op(self.tree[i], v)
			i -= i & -i
		return v
(N, Q) = map(int, input().split())
(*c,) = map(int, input().split())
q = [[] for _ in range(N + 1)]
for i in range(Q):
	(x, y) = map(int, input().split())
	q[y - 1].append([i, x - 1])
bit = BIT(N, add, 0)
finds = [-1] * (N + 1)
ans = [0] * Q
for i in range(N):
	if finds[c[i]] != -1:
		bit.update(finds[c[i]] + 1, -1)
	finds[c[i]] = i
	bit.update(finds[c[i]] + 1, 1)
	for (j, x) in q[i]:
		ans[j] = bit.query(i + 1) - bit.query(x)
for a in ans:
	print(a)


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
C = list(map(int, input().split()))
query = []
for i in range(Q):
	(l, r) = map(int, input().split())
	query.append((i, l, r))
query.sort(key=lambda x: x[2])

class BIT:
	from operator import add, sub
	X_unit = 0
	X_f = add
	X_f_rev = sub

	def __init__(self, seq):
		N = len(seq)
		self.N = N
		self.X = seq[:]
		for i in range(self.N):
			j = i + (i + 1 & -(i + 1))
			if j < self.N:
				self.X[j] = self.X_f(self.X[i], self.X[j])

	def set_val(self, i, x):
		while i < self.N:
			self.X[i] = self.X_f(self.X[i], x)
			i += i + 1 & -(i + 1)

	def cum_val(self, i):
		res = self.X_unit
		while i > -1:
			res = self.X_f(res, self.X[i])
			i -= i + 1 & -(i + 1)
		return res

	def fold(self, L, R):
		return self.X_f_rev(self.cum_val(R - 1), self.cum_val(L - 1))
GJ = [-1] * N
bit = BIT([0] * N)
ans = [0] * Q
st = 0
for i in range(N):
	if GJ[C[i] - 1] != -1:
		bit.set_val(GJ[C[i] - 1], -1)
	GJ[C[i] - 1] = i
	bit.set_val(i, 1)
	if st < Q:
		while query[st][2] == i + 1:
			ans[query[st][0]] = bit.fold(query[st][1] - 1, query[st][2])
			st += 1
			if st == Q:
				break
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
C = list(map(int, input().split()))
LR = [tuple(map(int, input().split())) for i in range(Q)]
qs = [[] for _ in range(N)]
for (i, (l, r)) in enumerate(LR):
	qs[l - 1].append((i, r - 1))
from collections import defaultdict
hist = defaultdict(lambda : -1)
nx = [-1] * N
for i in range(N - 1, -1, -1):
	nx[i] = hist[C[i]]
	hist[C[i]] = i

class BinaryIndexedTree:

	def __init__(self, size):
		self.N = size
		self.bit = [0] * (size + 1)

	def add(self, x, w):
		x += 1
		while x <= self.N:
			self.bit[x] += w
			x += x & -x

	def _sum(self, x):
		ret = 0
		while x > 0:
			ret += self.bit[x]
			x -= x & -x
		return ret

	def sum(self, l, r):
		return self._sum(r) - self._sum(l)

	def __str__(self):
		arr = [self.sum(i, i + 1) for i in range(self.N)]
		return str(arr)
bit = BinaryIndexedTree(N)
ans = [None] * Q
for l in range(N - 1, -1, -1):
	if nx[l] != -1:
		bit.add(nx[l], -1)
	for (i, r) in qs[l]:
		ans[i] = r - l + 1 + bit.sum(l, r + 1)
print(*ans, sep='\n')


import sys
import numpy as np
from numba import njit

def input():
	return sys.stdin.readline()
(N, Q) = list(map(int, input().split()))
C = np.array(input().split(), int)
queries = np.empty((Q, 2), int)
for q in range(Q):
	(l, r) = list(map(int, input().split()))
	queries[q][0] = l
	queries[q][1] = r
orderByR = np.argsort(queries[:, 1])
mostRightColorIndex = np.zeros(N + 1, int)
bitArray = np.zeros(N + 1, int)

@njit
def main(N, Q, C, queries, orderByR, mostRightColorIndex, bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += i & -i

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= i & -i
		return summary

	def sum(items, start, end):
		summary = sumFromStart(items, end) - sumFromStart(items, start - 1)
		return summary
	ans = [0] * Q
	qindex = 0
	for n in range(N):
		if Q <= qindex:
			break
		if 0 < mostRightColorIndex[C[n]]:
			add(N, bitArray, mostRightColorIndex[C[n]], -1)
		mostRightColorIndex[C[n]] = n + 1
		add(N, bitArray, n + 1, 1)
		while qindex < Q and n + 1 == queries[orderByR[qindex]][1]:
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex] = sum(bitArray, start, end)
			qindex += 1
	return ans
for a in main(N, Q, C, queries, orderByR, mostRightColorIndex, bitArray):
	print(a)


from sys import stdin
input = stdin.readline

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(n, q) = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
	color.append(v)
qry = [None] * q
ans = [0] * q
p = 0
for _ in ans:
	(l, r) = map(int, input().split())
	qry[p] = [l - 1, r, p]
	p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 1
bit = Bit(n)
for (l, r, i) in qry:
	if last_update_idx < r + 1:
		st = set()
		for j in range(last_update_idx, r + 1):
			if not color[j] in st and color[j] in dic:
				bit.add(dic[color[j]], -1)
			dic[color[j]] = j
			st.add(color[j])
		for v in st:
			bit.add(dic[v], 1)
		last_update_idx = r + 1
	ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
	print(v)


class fenwick_tree:

	def __init__(self, N):
		self.size = N
		self.tree = [0] * (N + 1)

	def sum_until(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def sum_acc(self, i, j):
		return self.sum_until(j) - self.sum_until(i - 1)

	def add(self, i, x):
		if i <= 0:
			return
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

def main():
	(N, Q) = (int(i) for i in input().split())
	C = [int(i) for i in input().split()]
	Query = [[] for _ in range(N + 1)]
	for j in range(Q):
		(le, ri) = (int(i) for i in input().split())
		Query[ri].append((le, j))
	Query.append((-1, -1, -1))
	lastappend = [-1] * (N + 1)
	bit = fenwick_tree(N)
	ans = [0] * Q
	for (i, a) in enumerate(C, start=1):
		if lastappend[a] != -1:
			bit.add(lastappend[a], -1)
		lastappend[a] = i
		bit.add(i, 1)
		for (le, j) in Query[i]:
			ri = i
			ans[j] = bit.sum_acc(le, ri)
	print(*ans, sep='\n')
main()


class Bit:

	def __init__(self, n):
		self.bl = n.bit_length()
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
import sys
input = sys.stdin.readline
from collections import defaultdict
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
lr = [tuple(map(int, input().split())) + (i,) for i in range(q)]
ans = [0] * q
lr.sort(key=lambda x: x[1])
bit = Bit(n + 2)
dc = defaultdict(int)
cnt = 0
for (L, R, p) in lr:
	L -= 1
	for i in range(cnt, R):
		if dc[a[i]]:
			l = dc[a[i]] - 1
			r = i
			bit.add(l + 2, 1)
			bit.add(r + 2, -1)
		else:
			bit.add(1, 1)
			bit.add(i + 2, -1)
		dc[a[i]] = i + 1
	ans[p] = bit.sum(L + 1)
	cnt = R
print(*ans, sep='\n')


def main():
	import sys
	input = sys.stdin.readline
	(n, q) = map(int, input().split())
	c = list(map(int, input().split()))
	ab = [[] for i in range(n)]
	lr = [[] for i in range(n)]
	num = [-1] * n
	for i in range(n):
		if num[c[i] - 1] != -1:
			ab[num[c[i] - 1]].append(i)
		num[c[i] - 1] = i
	for i in range(q):
		(l, r) = map(int, input().split())
		lr[l - 1].append((r - 1, i))
	ans = [-1] * q
	BIT = [0] * n
	for i in range(n - 1, -1, -1):
		for x in ab[i]:
			x += 1
			while x <= n:
				BIT[x - 1] += 1
				x = x + (x & -x)
		for (x, y) in lr[i]:
			X = x
			x += 1
			ret = 0
			while x != 0:
				ret += BIT[x - 1]
				x = x - (x & -x)
			ans[y] = X - i + 1 - ret
	for x in ans:
		print(x)
main()


from operator import itemgetter
(N, Q) = map(int, input().split())
C = [int(c) for c in input().split()]
L = [[int(l) for l in input().split()] for _ in range(Q)]
for i in range(Q):
	L[i].append(i)
M = pow(2, len(bin(N)) - 2)
BIT = [0] * (M + 1)
L.sort(key=itemgetter(1))
memo = [0] * (N + 1)
ans = [0] * Q
i = 1
j = 0
while i <= N:
	c = C[i - 1]
	idx = i
	if i <= L[j][1]:
		if memo[c] > 0:
			k = memo[c]
			while k <= M:
				BIT[k] -= 1
				k += k & -k
		memo[c] = i
		while idx <= M:
			BIT[idx] += 1
			idx += idx & -idx
	if i == L[j][1]:
		cnt = 0
		n = L[j][1]
		while n > 0:
			cnt += BIT[n]
			n -= n & -n
		n = L[j][0] - 1
		while n > 0:
			cnt -= BIT[n]
			n -= n & -n
		ans[L[j][2]] = cnt
		j += 1
		if j == Q:
			break
		elif L[j][1] == i:
			i -= 1
	i += 1
for a in ans:
	print(a)


import sys
input = sys.stdin.readline

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(N, Q) = map(int, input().split())
C = tuple(map(int, input().split()))
queries = []
for i in range(Q):
	(l, r) = map(int, input().split())
	queries.append((l, r, i))
queries.sort(key=lambda x: x[1])
b = Bit(N)
last = [None] * (N + 1)
cur = 1
ans = [0] * Q
for (l, r, i) in queries:
	while cur <= r:
		if last[C[cur - 1]] is not None:
			b.add(last[C[cur - 1]], -1)
		last[C[cur - 1]] = cur
		b.add(cur, 1)
		cur += 1
	ans[i] = b.sum(r) - b.sum(l - 1)
print(*ans, sep='\n')


def segfunc(x, y):
	return x + y
ide_ele = 0

class SegTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
st = SegTree([0] * n, segfunc, ide_ele)
lr = [[] for _ in range(n + 1)]
for i in range(q):
	(l, r) = map(int, input().split())
	lr[r] += [(l, i)]
d = {}
for i in range(n):
	if not d.get(c[i]):
		d[c[i]] = [i]
	else:
		d[c[i]] += [i]
for i in d:
	st.update(d[i][-1], 1)
ans = [0] * q
r = n
while r > 0:
	if lr[r]:
		(l, i) = lr[r].pop()
		ans[i] = st.query(l - 1, r)
	while not lr[r] and r > 0:
		if d[c[r - 1]]:
			st.update(d[c[r - 1]].pop(), 0)
		if d[c[r - 1]]:
			st.update(d[c[r - 1]][-1], 1)
		r -= 1
for i in ans:
	print(i)


import sys
input = sys.stdin.buffer.readline

class sumBIT:

	def __init__(self, N):
		self.N = N
		self.bit = [0 for _ in range(self.N + 1)]

	def __str__(self):
		ret = []
		for i in range(1, self.N + 1):
			ret.append(self.__getitem__(i))
		return '[' + ', '.join([str(a) for a in ret]) + ']'

	def __getitem__(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.N:
			self.bit[i] += x
			i += i & -i
(N, Q) = map(int, input().split())
C = list(map(int, input().split()))
LR = [list(map(int, input().split())) for _ in range(Q)]
Toask = [[] for _ in range(N + 1)]
for (i, (l, r)) in enumerate(LR):
	Toask[l].append((r, i))
bit = sumBIT(N + 3)
ans = [-1] * Q
Color = [-1] * (N + 1)
for l in reversed(range(1, N + 1)):
	c = C[l - 1]
	if Color[c] != -1:
		last = Color[c]
		bit.add(last, -1)
	bit.add(l, 1)
	for (r, ind) in Toask[l]:
		ans[ind] = str(bit[r])
	Color[c] = l
print('\n'.join(ans))


def solve():
	import sys
	input = sys.stdin.readline

	class FenwickTree:

		def __init__(self, size):
			self.size = size
			self.array = [0] * size

		def add(self, index, value):
			while index < self.size:
				self.array[index] += value
				index += index & -index

		def sum(self, index):
			answer = 0
			while index > 0:
				answer += self.array[index]
				index -= index & -index
			return answer

		def rangesum(self, start, end):
			return self.sum(end) - self.sum(start - 1)
	(N, Q) = map(int, input().split())
	(*c,) = map(int, input().split())
	tree = FenwickTree(N + 1)
	m = [tuple(map(int, input().split())) + (i,) for i in range(Q)]
	m.sort(key=lambda x: x[1])
	right = 0
	pos = [-1] * (N + 1)
	ans = [None] * Q
	for (l, r, idx) in m:
		for i in range(right, r):
			x = pos[c[i]]
			if x != -1:
				tree.add(x, -1)
			pos[c[i]] = i + 1
			tree.add(i + 1, 1)
		ans[idx] = tree.rangesum(l, r)
		right = r
	for i in ans:
		print(i)
solve()


def add(i, x):
	global BIT
	i += 1
	while i <= n:
		BIT[i] += x
		i += i & -i

def bitsum(i):
	x = 0
	i += 1
	while i > 0:
		x += BIT[i]
		i -= i & -i
	return x

def sums(l, r):
	return bitsum(r - 1) - bitsum(l - 1)
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
pi = [-1] * (n + 1)
ps = [[] for _ in range(n)]
qs = [[] for _ in range(n)]
for i in range(n):
	l = pi[c[i]]
	if l != -1:
		ps[l].append(i)
	pi[c[i]] = i
for i in range(q):
	(l, r) = map(int, input().split())
	(l, r) = (l - 1, r - 1)
	qs[l].append((r, i))
BIT = [0] * (n + 1)
ans = [None] * q
for x in range(n - 1, -1, -1):
	for y in ps[x]:
		add(y, 1)
	for (r, i) in qs[x]:
		ans[i] = r - x + 1 - bitsum(r)
for i in ans:
	print(i)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class Binary_Indexed_Tree_RAQ:

	def __init__(self, n):
		self.bit = [0] * (n + 1)
		self.n = n + 1

	def __add(self, ind, num):
		while ind <= self.n:
			self.bit[ind - 1] += num
			ind += ind & -ind

	def range_add(self, s, t, x):
		self.__add(s, x)
		self.__add(t + 1, -x)

	def query(self, i):
		ret = 0
		while i > 0:
			ret += self.bit[i - 1]
			i -= i & -i
		return ret
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
m = 10 ** 6 + 1
prev = [-1] * m
query = []
for i in range(q):
	(l, r) = map(int, input().split())
	(l, r) = (l - 1, r - 1)
	query.append((l, r, i))
ans = [0] * q
query.sort(key=lambda x: x[1])
BIT = Binary_Indexed_Tree_RAQ(n + 1)
cur = 0
for (l, r, i) in query:
	while cur <= r:
		ai = a[cur]
		BIT.range_add(prev[ai] + 2, cur + 1, 1)
		prev[ai] = cur
		cur += 1
	ans[i] = BIT.query(l + 1)
print(*ans, sep='\n')


import sys
from operator import itemgetter

def bit_add(arr, n, i, x):
	while i <= n:
		arr[i] += x
		i += i & -i

def bit_sum(arr, i):
	result = 0
	while i > 0:
		result += arr[i]
		i ^= i & -i
	return result
(n, q) = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
lr = list(map(int, sys.stdin.buffer.read().split()))
lll = lr[0::2]
rrr = lr[1::2]
idx = sorted(enumerate(rrr), key=itemgetter(1))
bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0
for (i, r) in idx:
	while p < r:
		c = ccc[p]
		before_appeared = appeared[c]
		if before_appeared != -1:
			bit_add(bit, bn, before_appeared + 2, -1)
		bit_add(bit, bn, p + 2, 1)
		appeared[c] = p
		p += 1
	ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, lll[i])
print('\n'.join(map(str, ans)))


import sys

def input():
	return sys.stdin.readline().strip()

def mapint():
	return map(int, input().split())
sys.setrecursionlimit(10 ** 9)
(N, Q) = mapint()
Cs = list(mapint())
LR = []
for i in range(Q):
	(l, r) = mapint()
	k = (r << 40) + (l << 20) + i
	LR.append(k)
LR.sort()
mask = (1 << 20) - 1
A = [0] * N

def add(A, a, w):
	x = a
	while x <= N:
		A[x - 1] += w
		x += x & -x

def sums(A, a):
	x = a
	S = 0
	while x != 0:
		S += A[x - 1]
		x -= x & -x
	return S
ans = [0] * Q
i = 0
last_appeared = [-1] * (N + 1)
for k in LR:
	ans_idx = k & mask
	l = k >> 20 & mask
	r = k >> 40
	while i < r:
		c = Cs[i]
		if last_appeared[c] == -1:
			last_appeared[c] = i + 1
			add(A, i + 1, 1)
		else:
			past = last_appeared[c]
			last_appeared[c] = i + 1
			add(A, past, -1)
			add(A, i + 1, 1)
		i += 1
	ans[ans_idx] = sums(A, r) - sums(A, l - 1)
for a in ans:
	print(a)


import sys
input = sys.stdin.readline

def query(i):
	res = 0
	while i > 0:
		res += BIT[i]
		i -= i & -i
	return res

def update(i, x):
	while i <= n:
		BIT[i] += x
		i += i & -i
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]
query_.sort(key=lambda x: x[1])
res = [0] * q
pos = [-1] * n
BIT = [0] * (n + 1)
p = 0
for (l, r, idx) in query_:
	for i in range(p, r):
		if pos[c[i] - 1] != -1:
			update(pos[c[i] - 1] + 1, -1)
		update(i + 1, 1)
		pos[c[i] - 1] = i
	res[idx] = query(r) - query(l - 1)
	p = r
for v in res:
	print(v)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
	(N, Q) = map(int, readline().split())
	C = list(map(int, readline().split()))
	LR = []
	for q in range(Q):
		(l, r) = map(int, readline().split())
		LR.append((r + 0.1, l, q))
	t = [-1] * (N + 1)
	sect = []
	for i in range(N):
		x = C[i]
		if t[x] != -1:
			sect.append((i + 1, t[x], -1))
		t[x] = i + 1
	sect += LR
	sort_index = sorted(list(range(len(sect))), key=lambda i: sect[i][0])
	bit = [0] * (N + 1)

	def add(i, val):
		while i <= N:
			bit[i] += val
			i += i & -i

	def sum(i):
		res = 0
		while i > 0:
			res += bit[i]
			i -= i & -i
		return res
	ans = [0] * Q
	for i in sort_index:
		(r, l, n) = sect[i]
		r = int(r)
		if n == -1:
			add(l, 1)
		else:
			t = sum(r) - sum(l - 1)
			ans[n] = r - l + 1 - t
	print('\n'.join(map(str, ans)))
main()


def main():
	(N, Q) = map(int, input().split())
	C = list(map(int, input().split()))
	LRI = []
	for i in range(Q):
		(l, r) = map(int, input().split())
		LRI.append((r, l, i))
	LRI.sort(key=lambda x: x[0])
	lastAppend = [-1] * (N + 1)
	BIT = [0] * (N + 1)

	def BIT_query(idx):
		res_sum = 0
		if idx == 0:
			return 0
		while idx > 0:
			res_sum += BIT[idx]
			idx -= idx & -idx
		return res_sum

	def BIT_update(idx, x):
		while idx <= N:
			BIT[idx] += x
			idx += idx & -idx
		return
	ANS = [0] * Q
	now = 1
	for (r, l, i) in LRI:
		while now <= r:
			c = C[now - 1]
			if lastAppend[c] == -1:
				BIT_update(now, 1)
			else:
				BIT_update(now, 1)
				BIT_update(lastAppend[c], -1)
			lastAppend[c] = now
			now += 1
		ANS[i] = BIT_query(r) - BIT_query(l - 1)
	print('\n'.join(map(str, ANS)))
main()


import sys
iim = lambda : map(int, sys.stdin.readline().rstrip().split())

def resolve():
	it = map(int, sys.stdin.read().split())
	X = 19
	(N, Q) = (next(it), next(it))
	X = Q.bit_length()
	(b1, br, bc) = ((1 << X) - 1, 2 * X + 1, 1 << X)
	Aa = [next(it) - 1 for i in range(N)]
	Aq = [0] * Q
	Ac = [0] * Q
	for i in range(Q):
		(l, r) = (next(it) - 1, next(it) - 1)
		Aq[i] = r << X | i
		Ac[i] = l
	Aq.sort()
	dp = [0] * N
	N1 = (2 * N + 1) // 2
	dp2 = [0] * (N1 * 2)
	ans = [0] * Q
	offset = 0
	for arg in Aq:
		r = arg >> X
		i = arg & b1
		for j in range(offset, r + 1):
			ci = Aa[j]
			lo = N1 + dp[ci]
			hi = N1 + j
			while lo < hi:
				if lo & 1:
					dp2[lo] += 1
					lo += 1
				if not hi & 1:
					dp2[hi] += 1
					hi -= 1
				lo >>= 1
				hi >>= 1
			if lo == hi:
				dp2[lo] += 1
			dp[ci] = j + 1
		offset = r + 1
		l = Ac[i]
		num = 0
		j = l + N1
		while j > 0:
			num += dp2[j]
			j >>= 1
		ans[i] = num
	print(*ans, sep='\n')
resolve()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)

	def add(self, i, x=1):
		i += 1
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get_sum(self, i):
		i += 1
		x = 0
		while i > 0:
			x += self.data[i]
			i -= i & -i
		return x

	def get_sum_range(self, l, r):
		return self.get_sum(r - 1) - self.get_sum(l - 1)

def main():
	(N, Q) = map(int, readline().split())
	C = list(map(int, readline().split()))
	LR = map(int, read().split())
	prev = [-1] * (N + 1)
	ps = [[] for _ in range(N)]
	for (i, c) in enumerate(C):
		if prev[c] != -1:
			ps[prev[c]].append(i)
		prev[c] = i
	qs = [[] for _ in range(N)]
	for (i, (l, r)) in enumerate(zip(*[iter(LR)] * 2)):
		qs[l - 1].append((r - 1, i))
	ans = [0] * Q
	bit = BIT(N)
	for l in range(N - 1, -1, -1):
		for r in ps[l]:
			bit.add(r)
		for (r, i) in qs[l]:
			ans[i] = r - l + 1 - bit.get_sum(r)
	print('\n'.join(map(str, ans)), sep='\n')
	return
main()


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
(*c,) = map(int, input().split())
qu = [list(map(int, input().split())) + [i] for i in range(q)]
qu.sort(key=lambda x: x[1])
bit = [0] * (n + 1)
last = [-1] * (n + 1)

def add(t, x):
	while t <= n:
		bit[t] += x
		t += t & -t

def query(t):
	res = 0
	while t:
		res += bit[t]
		t -= t & -t
	return res
used = 1
ans = [0] * q
for (l, r, i) in qu:
	while used <= r:
		add(used, 1)
		if last[c[used - 1]] >= 0:
			add(last[c[used - 1]], -1)
		last[c[used - 1]] = used
		used += 1
	ansi = query(r) - query(l - 1)
	ans[i] = ansi
for ansi in ans:
	print(ansi)


import sys, heapq
input = sys.stdin.readline
(n, q) = map(int, input().split())
c = [int(x) - 1 for x in input().split()]
que = []
for i in range(q):
	(l, r) = map(int, input().split())
	que.append((l, r, i))

class SegTree(object):

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.num = n

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.BIT[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.num:
			self.BIT[i] += x
			i += i & -i
que.sort(key=lambda x: -x[1])
ans = [None] * q
last = [-1] * n
BIT = SegTree(n)
for i in range(1, n + 1):
	if last[c[i - 1]] != -1:
		BIT.add(last[c[i - 1]], -1)
	last[c[i - 1]] = i
	BIT.add(i, 1)
	while que and que[-1][1] == i:
		(l, r, x) = que.pop()
		ans[x] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')


class BIT:

	def __init__(self, size):
		self.size = size
		self.data = [0] * (size + 1)

	def add(self, index, value=1):
		while index <= self.size:
			self.data[index] += value
			index += index & -index

	def sum(self, index):
		ret = 0
		while index:
			ret += self.data[index]
			index -= index & -index
		return ret

	def search(self, val):
		i = 0
		s = 0
		step = 1 << self.size.bit_length() - 1
		while step:
			if i + step <= self.size and s + self.data[i + step] < val:
				i += step
				s += self.data[i]
			step //= 2
		return i + 1
(N, Q) = map(int, input().split())
C = [-1] + list(map(int, input().split()))
tree = BIT(N)
query = [[] for _ in range(N + 1)]
for q in range(Q):
	(l, r) = map(int, input().split())
	query[r].append((q, l))
index = [-1] * (N + 1)
ans = [0] * Q
for r in range(1, N + 1):
	if index[C[r]] > 0:
		tree.add(index[C[r]], -1)
	tree.add(r, 1)
	index[C[r]] = r
	for (q, l) in query[r]:
		ans[q] = tree.sum(r) - tree.sum(l - 1)
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(Q):
	(l, r) = map(int, input().split())
	LR.append((l - 1, r - 1, i))

class FenwickTree(object):

	def __init__(self, n):
		self._bit = [0] * (n + 1)
		self.n = n + 1

	def add(self, i, a):
		i += 1
		while i < self.n:
			self._bit[i] += a
			i += i & -i

	def sum(self, i):
		i += 1
		ret = 0
		while i > 0:
			ret += self._bit[i]
			i -= i & -i
		return ret

def solve():
	memo = [-1] * N
	ST = []
	nst = 0
	for (i, c) in enumerate(C[::-1]):
		if memo[c - 1] >= 0:
			ST.append((N - i - 1, memo[c - 1]))
			nst += 1
		memo[c - 1] = N - i - 1
	LR.sort(reverse=True, key=lambda x: x[0])
	ans = [0 for _ in range(Q)]
	ft = FenwickTree(N + 1)
	j = 0
	for (l, r, i) in LR:
		while j < nst and ST[j][0] >= l:
			ft.add(ST[j][1], 1)
			j += 1
		ans[i] = r - l + 1 - ft.sum(r)
	return ans
print('\n'.join(map(str, solve())))


class BIT:

	def __init__(self, n):
		self.size = n + 1
		self.bit = [0] * self.size

	def add(self, i, x):
		while i < self.size:
			self.bit[i] += x
			i += i & -i

	def sumup(self, i):
		res = 0
		while i > 0:
			res += self.bit[i]
			i -= i & -i
		return res

	def query(self, i, j):
		return self.sumup(j) - self.sumup(i - 1)
(N, Q) = map(int, input().split())
C = list(map(int, input().split()))
X = []
for i in range(Q):
	(l, r) = map(int, input().split())
	X.append((i, l, r))
X.sort(key=lambda x: x[2])
ans = [0] * Q
bit = BIT(N + 1)
last = [0] * (N + 1)
k = 0
for (i, l, r) in X:
	for j in range(k + 1, r + 1):
		if last[C[j - 1]] > 0:
			bit.add(last[C[j - 1]], -1)
		bit.add(j, 1)
		last[C[j - 1]] = j
	k = r
	ans[i] = bit.query(l, r)
print(*ans, sep='\n')


(n, q) = map(int, input().split())
cs = list(map(int, input().split()))
prevs = [-1] * (n + 1)
sts = [-1] * n
for (i, c) in enumerate(cs):
	c -= 1
	if prevs[c] != -1:
		sts[prevs[c]] = i
	prevs[c] = i
qs = [[] for i in range(n)]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	qs[l].append((r, i))

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 10)

	def add(self, x, w):
		while x <= self.n:
			self.bit[x] += w
			x += x & -x

	def sum(self, x):
		cnt = 0
		while x > 0:
			cnt += self.bit[x]
			x -= x & -x
		return cnt
bit = BIT(n)
ans = [0] * q
for l in range(n - 1, -1, -1):
	if sts[l] != -1:
		bit.add(sts[l], 1)
	for (r, i) in qs[l]:
		cnt = bit.sum(r)
		ans[i] = r - l + 1 - cnt
print(*ans, sep='\n')


import sys
input = sys.stdin.buffer.readline
(n, q) = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(q):
	(l, r) = map(int, input().split())
	LR.append((l, r, i))
LR.sort(key=lambda x: x[1])
BIT = [0] * (n + 1)

def update(idx, val):
	while idx <= n:
		BIT[idx] += val
		idx += idx & -idx

def query(idx):
	res = 0
	while idx > 0:
		res += BIT[idx]
		idx -= idx & -idx
	return res
pos = [-1] * (n + 1)

def func(idx):
	temp = C[idx]
	if pos[temp] == -1:
		pos[temp] = idx + 1
		update(idx + 1, 1)
	else:
		pre = pos[temp]
		pos[temp] = idx + 1
		update(pre, -1)
		update(idx + 1, 1)
ans = [0] * q
idx = 0
for i in range(q):
	(l, r, ans_num) = LR[i]
	l -= 1
	r -= 1
	while idx < r + 1:
		if idx < n:
			func(idx)
			idx += 1
		else:
			break
	res = 0
	res += query(r + 1)
	if l > 0:
		res -= query(l)
	ans[ans_num] = res
print(*ans, sep='\n')


class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
import sys
input = sys.stdin.buffer.readline
(n, q) = map(int, input().split())
clst = list(map(int, input().split()))
lr = []
for i in range(q):
	(l, r) = map(int, input().split())
	lr.append([l, r, i])
lr.sort(key=lambda x: x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = [-1 for _ in range(q)]
for (i, c) in enumerate(clst):
	bit.add(i + 1, 1)
	if last[c - 1] != -1:
		bit.add(last[c - 1] + 1, -1)
	last[c - 1] = i
	while lr[pos][1] == i + 1:
		l = lr[pos][0]
		r = lr[pos][1]
		ans[lr[pos][2]] = bit.sum(r) - bit.sum(l - 1)
		pos += 1
		if pos == q:
			break
	if pos == q:
		break
print(*ans, sep='\n')


import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.el = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
ques = []
from collections import defaultdict
ans = defaultdict(int)
for _ in range(q):
	(l, r) = map(int, input().split())
	ques.append((l, r))
sortques = sorted(ques, key=lambda x: x[1])
good = BIT(n + 1)
goodind = [-1] * n
last = 0
for x in range(q):
	(l, r) = sortques[x]
	if last != r:
		for i in range(last, r):
			if goodind[c[i] - 1] == -1:
				goodind[c[i] - 1] = i
				good.add(i + 1, 1)
			else:
				j = goodind[c[i] - 1]
				good.add(j + 1, -1)
				goodind[c[i] - 1] = i
				good.add(i + 1, 1)
	ans[l, r] = good.get(l - 1, r)
	last = r
for i in range(q):
	print(ans[ques[i]])


import sys
buf = sys.stdin.buffer
input = buf.readline

class BIT:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * (n + 1)

	def add(self, i, x):
		(n, tree) = (self.n, self.tree)
		while i <= n:
			tree[i] += x
			i += i & -i

	def sum(self, i):
		tree = self.tree
		s = 0
		while i:
			s += tree[i]
			i -= i & -i
		return s

def main():
	(n, q) = map(int, input().split())
	res = [0] * q
	(*c,) = map(int, input().split())
	q = [(i, l, r) for (i, (l, r)) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
	q.sort(key=lambda x: x[2])
	bit = BIT(n + 2)
	(add, sum) = (bit.add, bit.sum)
	b = [1] * (n + 1)
	j = 1
	for (i, l, r) in q:
		while j <= r:
			d = c[j - 1]
			j += 1
			k = b[d]
			b[d] = j
			add(k + 1, 1)
			add(j + 1, -1)
		res[i] = sum(l + 1)
	print(' '.join(map(str, res)))
main()


import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, size):
		self.bit = [0] * (size + 1)
		self.size = size

	def sum(self, i):
		i += 1
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.bit[i] += x
			i += i & -i

	def lower_bound(self, x):
		if x <= 0:
			return 0
		k = 1
		while k * 2 <= self.size:
			k *= 2
		j = 0
		while k > 0:
			if j + k <= self.size and self.bit[j + k] < x:
				x -= self.bit[j + k]
				j += k
			k //= 2
		return j
(N, Q) = map(int, input().split())
c = [0] + list(map(int, input().split()))
queries = [list(map(int, input().split())) + [i] for i in range(Q)]
queries.sort(key=lambda q: q[1])
last = [-1] * (N + 1)
ans = [0] * Q
bit = BIT(N + 1)
j = 0
for (l, r, i) in queries:
	while j < r:
		j += 1
		if last[c[j]] != -1:
			bit.add(last[c[j]], -1)
		bit.add(j, 1)
		last[c[j]] = j
	ans[i] = bit.sum(r) - bit.sum(l - 1)
print(*ans, sep='\n')


from collections import defaultdict
import sys

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def add(self, i, value):
		i = i + 1
		while i <= self.n:
			self.bit[i] += value
			i += i & -i

	def _sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def sum(self, l, r):
		return self._sum(r) - self._sum(l)
input = sys.stdin.readline
(N, Q) = map(int, input().split())
C = list(map(int, input().split()))
LR = [tuple(map(int, input().split())) for _ in range(Q)]
query = [[] for _ in range(N)]
for (i, (l, r)) in enumerate(LR):
	query[l - 1].append((i, r - 1))
hist = defaultdict(lambda : -1)
nx = [-1] * N
for i in range(N - 1, -1, -1):
	nx[i] = hist[C[i]]
	hist[C[i]] = i
bit = BIT(N)
ans = [None] * Q
for l in range(N - 1, -1, -1):
	if nx[l] != -1:
		bit.add(nx[l], -1)
	for (i, r) in query[l]:
		ans[i] = r - l + 1 + bit.sum(l, r + 1)
print(*ans, sep='\n')


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
(N, Q) = map(int, input().split())
C = list(map(int, input().split()))
by_R = [[] for _ in range(N + 1)]
for i in range(Q):
	(l, r) = map(lambda s: int(s) - 1, input().split())
	by_R[r + 1].append((l, i))
s = [0] * N

def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos - 1]
		pos &= pos - 1
	return res
diff = 0
ans = [-1] * Q
last = [-1] * (N + 1)
for (i, v) in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1
	update(i, 1)
	last[v] = i
	for (l, j) in by_R[i + 1]:
		ans[j] = diff - query(l)
print('\n'.join(map(str, ans)))


def A(i, x):
	while i < n + 2:
		t[i] += x
		i += i & -i
((n, q), c, *z) = [[*map(int, t.split())] for t in open(0)]
a = [0] * q
(j, *b) = t = [0] * (n + 2)
for (i, (l, r)) in sorted(zip(range(q), z), key=lambda x: x[1][1]):
	while j < r:
		d = c[j]
		j += 1
		A(b[d] + 1, 1)
		b[d] = j
		A(j + 1, -1)
	while l:
		a[i] += t[l]
		l -= l & -l
print(*a)


((n, q), c, *z) = [[*map(int, t.split())] for t in open(0)]
a = [0] * q
(j, *b) = t = [0] * 9 ** 6
for i in sorted(range(q), key=lambda x: z[x][1]):
	(l, r) = z[i]
	while j < r:
		d = c[j]
		j += 1
		(x, y, b[d]) = (b[d] + 1, j + 1, j)
		while x <= n:
			t[x] += 1
			x += x & -x
		while y <= n:
			t[y] -= 1
			y += y & -y
	while l:
		a[i] += t[l]
		l -= l & -l
print(*a)


import sys
input = sys.stdin.readline

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(n, q) = list(map(int, input().split()))
ball = list(map(int, input().split()))
h = Bit(n + 1)
L = {}
jump = {}
on = set()
for (i, b) in enumerate(ball):
	if b not in L:
		h.add(i + 1, 1)
		on.add(i + 1)
	if b in L:
		jump[L[b]] = i + 1
	L[b] = i + 1
Q = []
for _ in range(q):
	(l, r) = list(map(int, input().split()))
	Q.append((l, r))
LOO = list(Q)
Q.sort(key=lambda x: x[0])
c = 1
ans = {}
for (l, r) in Q:
	for i in range(c, l):
		if i in on:
			on.remove(i)
			h.add(i, -1)
			if i in jump:
				dest = jump[i]
				h.add(dest, 1)
				on.add(dest)
	tmp = h.sum(r) - h.sum(l - 1)
	ans[l, r] = tmp
	c = l
p = []
for q in LOO:
	p.append(ans[q])
print(*p, sep='\n')


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
c = [int(i) for i in input().split()]
lr = [[int(i) - 1 for i in input().split()] for _ in range(Q)]

class BinaryIndexedTree:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.n:
			self.tree[i] += x
			i += i & -i
BIT = BinaryIndexedTree(N + 5)
sch = [[i, l, r] for (i, (l, r)) in enumerate(lr)]
sch.sort(key=lambda x: x[2])
ret = [0] * Q
last = [-1] * (N + 1)
cur = 0
for (i, l, r) in sch:
	while cur <= r:
		BIT.add(cur + 1, 1)
		pos = last[c[cur]]
		if pos != -1:
			BIT.add(pos + 1, -1)
		last[c[cur]] = cur
		cur += 1
	ret[i] = BIT.sum(r + 1) - BIT.sum(l)
for r in ret:
	print(r)


(N, Q) = map(int, input().split())
BIT = [0] * (N + 1)

def BIT_query(idx):
	res_sum = 0
	while idx > 0:
		res_sum += BIT[idx]
		idx -= idx & -idx
	return res_sum

def BIT_update(idx, x):
	while idx <= N:
		BIT[idx] += x
		idx += idx & -idx
	return
c = [-1] + list(map(int, input().split()))
lastAppeared = [-1] * (N + 1)
ans = [0] * Q
queries = []
for q in range(Q):
	(l, r) = map(int, input().split())
	queries.append((l, r, q))
queries.sort(key=lambda x: x[1])
curR = 0
for i in range(Q):
	(l, r, q) = queries[i]
	while curR < r:
		curR += 1
		new = c[curR]
		last = lastAppeared[new]
		if last != -1:
			BIT_update(last, -1)
		lastAppeared[new] = curR
		BIT_update(curR, 1)
	ans[q] = BIT_query(r) - BIT_query(l - 1)
for i in range(Q):
	print(ans[i])


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from operator import itemgetter
(N, Q) = map(int, input().split())
C = [0] + list(map(int, input().split()))
QU = [list(map(int, input().split())) + [i] for i in range(Q)]
QU.sort(key=itemgetter(0))
LEN = N + 3
BIT = [0] * (LEN + 1)

def update(v, w):
	while v <= LEN:
		BIT[v] += w
		v += v & -v

def getvalue(v):
	ANS = 0
	while v != 0:
		ANS += BIT[v]
		v -= v & -v
	return ANS
NUM = [[] for i in range(N + 1)]
for (i, c) in enumerate(C):
	if i == 0:
		continue
	if NUM[c] == []:
		update(i, 1)
	NUM[c].append(i)
NUMIND = [0] * (N + 1)
ANS = [-1] * Q
ia = 1
for (x, y, ind) in QU:
	while ia != x:
		update(NUM[C[ia]][NUMIND[C[ia]]], -1)
		NUMIND[C[ia]] += 1
		if NUMIND[C[ia]] < len(NUM[C[ia]]):
			update(NUM[C[ia]][NUMIND[C[ia]]], 1)
		ia += 1
	ANS[ind] = getvalue(y)
sys.stdout.write(' '.join(map(str, ANS)) + '\n')


import sys
input = sys.stdin.readline
from collections import *

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.bit[i] += x
			i += i & -i

	def acc(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s
(N, Q) = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1] * N
ys = defaultdict(list)
for i in range(N):
	if prev[c[i] - 1] != -1:
		ys[prev[c[i] - 1]].append(i)
	prev[c[i] - 1] = i
que = defaultdict(list)
for i in range(Q):
	(l, r) = map(int, input().split())
	que[l - 1].append((i, r - 1))
idx = 0
bit = BIT(N)
ans = [-1] * Q
for x in range(N - 1, -1, -1):
	for y in ys[x]:
		bit.add(y, 1)
	for (i, r) in que[x]:
		ans[i] = r - x + 1 - bit.acc(r + 1)
for ans_i in ans:
	print(ans_i)


(n, q, *x) = map(int, open(0).read().split())
a = x[:n]
queries = [[] for _ in [0] * n]
for i in range(q):
	(l, r) = (x[n + i * 2], x[n + i * 2 + 1])
	l -= 1
	r -= 1
	queries[r].append((l, i))
lastAppeared = [0] * n
bit = [0] * (n + 1)
ans = [0] * q
for i in range(n):
	x = lastAppeared[a[i] - 1] + 1
	while x <= n + 1:
		bit[x - 1] -= 1
		x += x & -x
	x = i + 2
	while x <= n + 1:
		bit[x - 1] += 1
		x += x & -x
	lastAppeared[a[i] - 1] = i + 1
	for (l, ind) in queries[i]:
		x = i + 2
		while x:
			ans[ind] += bit[x - 1]
			x -= x & -x
		x = l + 1
		while x:
			ans[ind] -= bit[x - 1]
			x -= x & -x
print(*ans)


def main():
	import sys
	input = sys.stdin.buffer.readline
	(N, Q) = map(int, input().split())
	(*C,) = map(int, input().split())
	last = [-1] * (N + 1)
	P = [[] for _ in [0] * (N + 1)]
	for (i, c) in enumerate(C):
		if last[c] != -1:
			P[last[c]].append(i + 1)
		last[c] = i + 1
	queries = [[] for _ in [0] * (N + 1)]
	for i in range(Q):
		(l, r) = map(int, input().split())
		queries[l].append((r, i))

	class BIT:

		def __init__(self, n, x=1):
			self.n = n
			self.T = [0] * (n + 1)

		def add(self, i, x):
			while i <= self.n:
				self.T[i] += x
				i += i & -i

		def lsum(self, i):
			ret = 0
			while i > 0:
				ret += self.T[i]
				i ^= i & -i
			return ret
	A = BIT(N)
	ans = [0] * Q
	for l in range(N, 0, -1):
		for cr in P[l]:
			A.add(cr, 1)
		for (r, i) in queries[l]:
			ans[i] = r - l + 1 - A.lsum(r)
	print(*ans, sep='\n')
main()


I = lambda : map(int, input().split())
N = 1048575
(n, q) = I()
c = list(I())
Q = []
R = range
for i in R(q):
	(l, r) = I()
	Q.append(l << 40 | r << 20 | i)
Q.sort()
A = [[] for i in R(N)]
for i in R(n):
	A[c[i]].append(i)
B = [0] * N

def P(i, x):
	i += 1
	while i <= n:
		B[i] += x
		i += i & -i
for i in A:
	if i:
		P(i[0], 1)
		i.reverse()
t = 0
o = [0] * q
for x in Q:
	l = (x >> 40) - 1
	r = x >> 20 & N
	i = x & N
	while t < l:
		b = A[c[t]]
		P(b[-1], -1)
		b.pop()
		if b:
			P(b[-1], 1)
		t += 1
	while r:
		o[i] += B[r]
		r -= r & -r
	while l:
		o[i] -= B[l]
		l -= l & -l
for i in o:
	print(i)


import sys
input = sys.stdin.buffer.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
queries = [[] for _ in [0] * n]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	queries[r].append((l, i))
lastAppeared = [0] * n
bit = [0] * (n + 1)
ans = [0] * q
for i in range(n):
	x = lastAppeared[a[i] - 1] + 1
	while x <= n + 1:
		bit[x - 1] -= 1
		x += x & -x
	x = i + 2
	while x <= n + 1:
		bit[x - 1] += 1
		x += x & -x
	lastAppeared[a[i] - 1] = i + 1
	for (l, ind) in queries[i]:
		x = i + 2
		while x:
			ans[ind] += bit[x - 1]
			x -= x & -x
		x = l + 1
		while x:
			ans[ind] -= bit[x - 1]
			x -= x & -x
print(*ans)


from collections import deque
(N, Q) = map(int, input().split())

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.el = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)
query = []
C = list(map(int, input().split()))
for i in range(Q):
	(l, r) = map(int, input().split())
	query.append((l, r, i))
query = sorted(query, key=lambda x: -x[1])
state = [-1] * N
seg = BIT(N + 1)
ans = [0] * Q
for i in range(N):
	while query and query[-1][1] < i + 1:
		(l, r, j) = query.pop()
		ans[j] = r - l + 1 - seg.get(l - 1, r)
	c = C[i]
	if state[c - 1] == -1:
		state[c - 1] = i + 1
	else:
		idx = state[c - 1]
		seg.add(idx, 1)
		state[c - 1] = i + 1
	while query and query[-1][1] == i + 1:
		(lq, rq, j) = query.pop()
		ans[j] = rq - lq + 1 - seg.get(lq - 1, rq)
for a in ans:
	print(a)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class BitSum:

	def __init__(self, n):
		self.n = n + 1
		self.table = [0] * self.n

	def add(self, i, x):
		i += 1
		while i < self.n:
			self.table[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		res = 0
		while i > 0:
			res += self.table[i]
			i -= i & -i
		return res
(n, q) = MI()
cc = LI()
lri = []
mx = 500005
for i in range(q):
	(l, r) = MI()
	l -= 1
	lri.append((l, r - 1, i))
lri.sort(key=lambda x: x[1])
last = [-1] * mx
st = BitSum(mx)
ans = [0] * q
now = 0
for (l, r, i) in lri:
	for j in range(now, r + 1):
		c = cc[j]
		pre = last[c]
		if pre != -1:
			st.add(pre, -1)
		last[c] = j
		st.add(j, 1)
	now = r + 1
	ans[i] = st.sum(r) - st.sum(l - 1)
print(*ans, sep='\n')


def main():
	import os, io
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
	(N, Q) = map(int, input().split())
	(*C,) = map(int, input().split())
	last = [-1] * (N + 1)
	P = [[] for _ in [0] * (N + 1)]
	for (i, c) in enumerate(C):
		if last[c] != -1:
			P[last[c]].append(i + 1)
		last[c] = i + 1
	queries = [[] for _ in [0] * (N + 1)]
	for i in range(Q):
		(l, r) = map(int, input().split())
		queries[l].append((r, i))

	def add(A, i, x):
		while i <= N:
			A[i] += x
			i += i & -i

	def sum(A, i):
		ret = 0
		while i:
			ret += A[i]
			i ^= i & -i
		return ret
	A = [0] * (N + 1)
	ans = [0] * Q
	for l in range(N, 0, -1):
		for cr in P[l]:
			add(A, cr, 1)
		for (r, i) in queries[l]:
			ans[i] = r - l + 1 - sum(A, r)
	print(*ans, sep='\n')
main()


class BIT:

	def __init__(self, N, val=0):
		self.data = [val] * (N + 1)
		self.N = N

	def add_at(self, idx, val):
		i = idx + 1
		while i <= self.N:
			self.data[i] += val
			i += i & -i

	def sum_to(self, idx):
		res = 0
		i = idx + 1
		while i > 0:
			res += self.data[i]
			i -= i & -i
		return res

	def sum_in(self, l, r):
		return self.sum_to(r) - self.sum_to(l - 1)

class Query:

	def __init__(self, i, l, r):
		self.i = i
		self.l = l
		self.r = r
(N, Q) = map(int, input().split())
C = list(map(int, input().split()))
queries = [[] for _ in range(N)]
for i in range(Q):
	(l, r) = map(int, input().split())
	(l, r) = (l - 1, r - 1)
	queries[r].append(Query(i, l, r))
bit = BIT(N)
last = [-1] * (max(C) + 1)
query_idx = 0
ans = [-1] * Q
for (i, c) in enumerate(C):
	if last[c] != -1:
		bit.add_at(last[c], -1)
	bit.add_at(i, +1)
	last[c] = i
	for q in queries[i]:
		ans[q.i] = bit.sum_in(q.l, q.r)
print('\n'.join(map(str, ans)))


def main():

	def add(i, x):
		i += 1
		while i <= n:
			bit[i - 1] += x
			i += i & -i

	def sum_sub(i):
		a = 0
		i += 1
		while i:
			a += bit[i - 1]
			i -= i & -i
		return a

	def sum(i, j):
		a = sum_sub(j + 1)
		if i != 0:
			a -= sum_sub(i - 1)
		return a
	(n, q, *x) = map(int, open(0).read().split())
	a = x[:n]
	queriess = []
	for i in range(q):
		(l, r) = x[n + i * 2:n + (i + 1) * 2]
		l -= 1
		r -= 1
		queriess.append(r << 40 | l << 20 | i)
	ans = [0] * q
	queriess.sort()
	queries = []
	for i in range(q):
		ind = queriess[i] % (1 << 20)
		queriess[i] >>= 20
		l = queriess[i] % (1 << 20)
		queriess[i] >>= 20
		r = queriess[i]
		queries.append((r, l, ind))
	queries.append((10 * 20, 0, 0))
	lastAppeared = [-1] * n
	bit = [0] * n
	j = 0
	for i in range(n):
		if lastAppeared[a[i] - 1] != -1:
			add(lastAppeared[a[i] - 1], -1)
			add(i, 1)
			lastAppeared[a[i] - 1] = i
		else:
			add(i, 1)
			lastAppeared[a[i] - 1] = i
		while queries[j][0] == i:
			(r, l, ind) = queries[j]
			j += 1
			ans[ind] = sum(l, r - 1)
	print(*ans)
main()


import sys
input = sys.stdin.readline

def main():
	(N, Q) = map(int, input().split())
	bit = [0] * (N + 1)

	def add(x, a):
		while x <= N:
			bit[x] += a
			x += x & -x

	def sum(x):
		ret = 0
		while x != 0:
			ret += bit[x]
			x -= x & -x
		return ret
	c = list(map(int, input().split()))
	lr = [None] * Q
	for i in range(Q):
		(l, r) = map(int, input().split())
		lr[i] = (i, l, r)
	lr.sort(key=lambda x: x[2])
	ans = [None] * Q
	last_idx = [-1] * (N + 1)
	j = 0
	for (i, l, r) in lr:
		while j < r:
			if last_idx[c[j]] == -1:
				last_idx[c[j]] = j
			else:
				add(last_idx[c[j]] + 1, -1)
				last_idx[c[j]] = j
			add(j + 1, 1)
			j += 1
		ans[i] = sum(r) - sum(l - 1)
	for a in ans:
		print(a)
main()


BIT = [0] * ((1 << 19) + 1)

def add(i, x):
	while i <= 1 << 19:
		BIT[i] += x
		i += i & -i

def query(i):
	res = 0
	while i > 0:
		res += BIT[i]
		i -= i & -i
	return res
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
Q = [[] for i in range(n)]
for i in range(q):
	(l, r) = map(int, input().split())
	Q[r - 1].append([l - 1, i])
l = [-1] * n
a = [-1] * q
add(1, n)
for i in range(n):
	add(l[c[i] - 1] + 2, -1)
	add(i + 2, 1)
	l[c[i] - 1] = i
	for j in Q[i]:
		a[j[1]] = query(1 << 19) - query(j[0] + 1)
print(*a, sep='\n')


import sys

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LIR(n):
	return [[i, LI()] for i in range(n)]

def solve():

	def add(i, x):
		while i < len(bit):
			bit[i] += x
			i += i & -i

	def sum_(i):
		res = 0
		while i > 0:
			res += bit[i]
			i -= i & -i
		return res
	(n, Q) = LI()
	c = LI()
	c = [0] + c
	q = LIR(Q)
	q.sort(key=lambda x: x[1][1])
	bit = [0] * (n + 2)
	i = 1
	p = [None] * (n + 1)
	ans = [0] * Q
	s = 0
	for (ind, (l, r)) in q:
		l -= 1
		while i <= r:
			ci = c[i]
			j = p[ci]
			if j is not None:
				add(j, 1)
			else:
				s += 1
			p[ci] = i
			i += 1
		ans[ind] = s - l + sum_(l)
	for i in ans:
		print(i)
	return
solve()


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
C = [list(map(int, input().split())) + [i] for i in range(q)]
for i in range(q):
	C[i][0] -= 1
	C[i][1] -= 1
for i in range(n):
	A[i] -= 1

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
B = Bit(n + 1)
ANS = [-1] * q
C.sort(key=lambda x: x[1])
G = [-1] * (max(A) + 1)
ind = 0
for i in range(n):
	a = A[i]
	if G[a] != -1:
		B.add(G[a] + 1, -1)
	G[a] = i
	B.add(G[a] + 1, 1)
	while ind < q and C[ind][1] == i:
		ANS[C[ind][2]] = B.sum(C[ind][1] + 1) - B.sum(C[ind][0] + 1 - 1)
		ind += 1
for i in range(q):
	print(ANS[i])


(n, q) = map(int, input().split())
c = tuple(map(int, input().split()))
qs = [[] for _ in range(n)]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	qs[l].append((r, i))

class BIT:

	def __init__(self, n):
		self.num = n
		self.dat = [0] * (self.num + 1)
		self.depth = n.bit_length()

	def add(self, i, x):
		i += 1
		while i <= self.num:
			self.dat[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		s = 0
		while i > 0:
			s += self.dat[i]
			i -= i & -i
		return s

	def lower_bound(self, x):
		sum_ = 0
		pos = 0
		for i in range(self.depth, -1, -1):
			k = pos + (1 << i)
			if k <= self.num and sum_ + self.dat[k] < x:
				sum_ += self.dat[k]
				pos += 1 << i
		return (pos, sum_)
ps = [-1 for _ in range(n)]
pi = [-1 for _ in range(n + 1)]
for i in range(n):
	l = pi[c[i]]
	if l != -1:
		ps[l] = i
	pi[c[i]] = i
d = BIT(n)
ans = [0 for _ in range(q)]
for x in range(n - 1, -1, -1):
	if ps[x] != -1:
		d.add(ps[x], 1)
	for (r, i) in qs[x]:
		ans[i] = r - x + 1 - d.sum(r)
for i in range(q):
	print(ans[i])


import sys
input = sys.stdin.buffer.readline
(N, Q) = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(Q):
	(l, r) = map(int, input().split())
	query.append((l - 1, r, i))
query.sort(key=lambda x: x[1])
rt = 0
L = [None for _ in range(N)]
res = [0 for _ in range(Q)]
bit = [0 for _ in range(N + 1)]
for (l, r, id) in query:
	while rt < r:
		if L[C[rt]] is not None:
			idx = L[C[rt]] + 1
			while idx <= N:
				bit[idx] -= 1
				idx += idx & -idx
		L[C[rt]] = rt
		idx = rt + 1
		while idx <= N:
			bit[idx] += 1
			idx += idx & -idx
		rt += 1
	sr = 0
	sl = 0
	idx = r
	while idx:
		sr += bit[idx]
		idx -= idx & -idx
	idx = l
	while idx:
		sl += bit[idx]
		idx -= idx & -idx
	res[id] = sr - sl
print('\n'.join(map(str, res)))


class BIT:

	def __init__(self, n):
		self.size = n + 1
		self.bit = [0] * self.size

	def add(self, i, x):
		while i < self.size:
			self.bit[i] += x
			i += i & -i

	def sumup(self, i):
		res = 0
		while i > 0:
			res += self.bit[i]
			i -= i & -i
		return res

	def query(self, i, j):
		return self.sumup(j) - self.sumup(i - 1)
(N, Q) = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]
ans = [0] * Q
last_appeared = [0] * (N + 1)
bit = BIT(N + 1)
rm = 0
for (i, (l, r)) in sorted(enumerate(X), key=lambda x: x[1][1]):
	for j in range(rm + 1, r + 1):
		if last_appeared[C[j - 1]] > 0:
			bit.add(last_appeared[C[j - 1]], -1)
		last_appeared[C[j - 1]] = j
		bit.add(j, 1)
	rm = r
	ans[i] = bit.query(l, r)
print(*ans, sep='\n')


import sys

def main():
	(n, q) = map(int, sys.stdin.readline().split())
	c = list(map(int, sys.stdin.readline().split()))
	fenwick = [0] * n

	def add(i, v):
		while i < n:
			fenwick[i] += v
			i = i | i + 1

	def get(r):
		res = 0
		while r >= 0:
			res += fenwick[r]
			r = (r & r + 1) - 1
		return res

	def get_seg(l, r):
		return get(r) - get(l - 1)
	by_r = [[] for i in range(n)]
	for t in range(q):
		(l, r) = map(int, sys.stdin.readline().split())
		(l, r) = (l - 1, r - 1)
		by_r[r].append((l, t))
	last_ent = [-1] * (n + 1)
	ans = [0] * q
	for r in range(n):
		p = last_ent[c[r]]
		if p != -1:
			add(p, -1)
		last_ent[c[r]] = r
		add(r, 1)
		for quer in by_r[r]:
			(l, num) = quer
			ans[num] = get_seg(l, r)
	print('\n'.join([str(x) for x in ans]))
main()


import sys
from collections import defaultdict
input = sys.stdin.readline
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
lr = []
for i in range(q):
	(l, r) = map(int, input().split())
	lr.append((l, r, i))
left_index_dict = {}
d = defaultdict(int)
for (i, ci) in enumerate(c):
	index = d[ci]
	if index in left_index_dict:
		left_index_dict[index].append(i + 1)
	else:
		left_index_dict[index] = [i + 1]
	d[ci] = i + 1
lr.sort(key=lambda x: x[0])
index = list(left_index_dict.keys())
index.sort()
i = 0
N = n
bit = [0] * (N + 1)

def sum(i):
	s = 0
	while i > 0:
		s += bit[i]
		i -= i & -i
	return s

def add(i, x):
	while i <= N:
		bit[i] += x
		i += i & -i
ans = [0] * q
for (l, r, _i) in lr:
	while i < len(index) and index[i] < l:
		for j in left_index_dict[index[i]]:
			add(j, 1)
		i += 1
	ans[_i] = sum(r) - sum(l - 1)
for ansi in ans:
	print(ansi)


class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(n, q) = map(int, input().split())
c = list(map(int, input().split()))
last = [-1] * n
foradd = [[] for i in range(n)]
for i in range(n):
	if last[c[i] - 1] != -1:
		foradd[last[c[i] - 1]].append(i)
	last[c[i] - 1] = i
forsum = [[] for i in range(n)]
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	forsum[l].append([r, i])
bit = Bit(n)
ans = [-1] * q
for i in range(n - 1, -1, -1):
	for j in foradd[i]:
		bit.add(j, 1)
	for j in forsum[i]:
		ans[j[1]] = j[0] - i + 1 - bit.sum(j[0])
print(*ans, sep='\n')


NN = 19
XX = [0] * (2 ** (NN + 1) - 1)

def addvalue(j, x):
	i = 2 ** NN + j - 1
	while i >= 0:
		XX[i] += x
		i = (i - 1) // 2

def rangesum(a, b):
	l = a + (1 << NN)
	r = b + (1 << NN)
	s = 0
	while l < r:
		if l % 2:
			s += XX[l - 1]
			l += 1
		if r % 2:
			r -= 1
			s += XX[r - 1]
		l >>= 1
		r >>= 1
	return s
(N, Q) = map(int, input().split())
C = [int(a) - 1 for a in input().split()]
X = [[] for _ in range(N)]
for i in range(Q):
	(l, r) = map(int, input().split())
	X[r - 1].append((l - 1, i))
last = [-1] * N
ANS = [-1] * Q
addvalue(1, N)
for r in range(N):
	c = C[r]
	addvalue(last[c] + 2, -1)
	addvalue(r + 2, 1)
	last[c] = r
	for (l, i) in X[r]:
		ANS[i] = rangesum(l + 2, 1 << NN)
print(*ANS, sep='\n')


import sys
iim = lambda : map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
	while i < n:
		a[i] += x
		i += i & -i

def bit_add2(a, i, j, n, x):
	if j << 1 < n:
		n = 1 << j.bit_length()
	while i < n:
		a[i] += x
		i += i & -i
	while j < n:
		a[j] -= x
		j += j & -j

def bit_sum(a, i):
	res = 0
	while i > 0:
		res += a[i]
		i ^= i & -i
	return res

def resolve():
	it = map(int, sys.stdin.read().split())
	(N, Q) = (next(it), next(it))
	X = Q.bit_length()
	mask = (1 << X) - 1
	Aa = [next(it) - 1 for i in range(N)]
	Aq = [0] * Q
	Ac = [0] * Q
	for i in range(Q):
		(l, r) = (next(it), next(it))
		Aq[i] = r << X | i
		Ac[i] = l
	Aq.sort()
	dp = [1] * N
	N1 = N + 1
	bit = [0] * N1
	ans = [0] * Q
	offset = 0
	for arg in Aq:
		r = arg >> X
		i = arg & mask
		for j in range(offset, r):
			ci = Aa[j]
			j += 2
			j0 = dp[ci]
			bit_add2(bit, j0, j, N1, 1)
			dp[ci] = j
		offset = r
		l = Ac[i]
		ans[i] = bit_sum(bit, l)
	print(*ans, sep='\n')
resolve()


import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, n):
		self.n = n + 1
		self.BIT = [0] * self.n

	def add(self, i, x):
		idx = i
		while idx < self.n:
			self.BIT[idx] += x
			idx += idx & -idx

	def _sum(self, i):
		ret = 0
		idx = i
		while idx > 0:
			ret += self.BIT[idx]
			idx -= idx & -idx
		return ret

	def sum(self, l, r):
		return self._sum(r) - self._sum(l - 1)

	def value(self, i):
		return self._sum(i) - self._sum(i - 1)
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
query = []
for i in range(q):
	(l, r) = map(int, input().split())
	query.append((l, r, i))
query = sorted(query, key=lambda x: x[0])
ans = [0] * q
bit = BIT(n)
pos_now = [-1] * (n + 1)
pos_prev = [-1] * (n + 1)
dic = {}
for i in range(n):
	val = arr[i]
	dic[i + 1] = -1
	if pos_now[val] == -1:
		bit.add(i + 1, 1)
		pos_now[val] = i + 1
	if pos_prev[val] != -1:
		dic[pos_prev[val]] = i + 1
	pos_prev[val] = i + 1
prev = 1
for (l, r, id) in query:
	while prev < l:
		val = arr[prev - 1]
		if dic[pos_now[val]] != -1:
			pos_now[val] = dic[pos_now[val]]
			bit.add(pos_now[val], 1)
		prev += 1
	ans[id] = bit.sum(l, r)
for val in ans:
	print(val)


from sys import exit, stdin
import copy
from collections import deque, Counter

class BIT:

	def __init__(self, a=0):
		self.n = a
		self.d = [0] * (a + 1)

	def add(self, i, x=1):
		i += 1
		while i <= self.n:
			self.d[i] += x
			i += i & -i

	def sum(self, *i):
		if len(i) == 1:
			x = 0
			tmp = i[0] + 1
			while tmp:
				x += self.d[tmp]
				tmp -= tmp & -tmp
			return x
		else:
			return sum(self, i[1] - 1) - sum(self, i[0] - 1)
(N, Q) = map(int, stdin.readline().split())
C = list(map(int, stdin.readline().split()))
app = [-1] * (N + 1)
ps = [[] for _ in range(N)]
for i in range(N):
	tmp = app[C[i]]
	if tmp != -1:
		ps[tmp].append(i)
	app[C[i]] = i
qs = [[] for _ in range(N)]
for i in range(Q):
	(l, r) = map(int, stdin.readline().split())
	l -= 1
	r -= 1
	qs[l].append(copy.deepcopy([r, i]))
ans = [0] * Q
d = BIT(N)
for x in range(N - 1, -1, -1):
	for y in ps[x]:
		d.add(y, 1)
	for p in qs[x]:
		r = p[0]
		i = p[1]
		ans[i] = r - x + 1 - d.sum(r)
for re in ans:
	print(re)