I=lambda:list(map(int,input().split()))

N=0xfffff

n,q=I()

c=list(I())

Q=[]

for i in range(q):l,r=I();Q.append(l<<40|r<<20|i)

Q.sort()

A=[[]for i in range(N)]

for i,x in enumerate(c):A[x].append(i)

B=[0]*N

def P(i,x):

	i+=1

	while i<=n:B[i]+=x;i+=i&-i

def G(i):

	s=0

	while i:s+=B[i];i-=i&-i

	return s

for i in A:

	if i:P(i[0],1);i.reverse()

t=0

o=[0]*q

for x in Q:

	l=x>>40

	r=x>>20&N

	i=x&N

	while t+1<l:

		b=A[c[t]]

		P(b[-1],-1)

		b.pop()

		if b:P(b[-1],1)

		t+=1

	o[i]=G(r)-G(l-1)

for i in o:print(i)
I=lambda:list(map(int,input().split()))

N=0xfffff

n,q=I()

c=list(I())

Q=[]

for i in range(q):l,r=I();Q.append(l<<40|r<<20|i)

Q.sort()

A=[[]for i in range(N)]

for i in range(n):A[c[i]].append(i)

B=[0]*N

def P(i,x):

	i+=1

	while i<=n:B[i]+=x;i+=i&-i

def G(i):

	s=0

	while i:s+=B[i];i-=i&-i

	return s

for i in A:

	if i:P(i[0],1);i.reverse()

t=0

o=[0]*q

for x in Q:

	l=x>>40

	r=x>>20&N

	i=x&N

	while t+1<l:

		b=A[c[t]]

		P(b[-1],-1)

		b.pop()

		if b:P(b[-1],1)

		t+=1

	o[i]=G(r)-G(l-1)

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


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


def G(i):
    s = 0
    while i:
        s += B[i]
        i -= i & -i
    return s


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

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


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


def G(i):
    s = 0
    while i:
        s += B[i]
        i -= i & -i
    return s


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

-for i, x in enumerate(c): -    A[x].append(i) +for i in range(n): +    A[c[i]].append(i)