import sys
input = sys.stdin.readline
from math import sqrt
mem = 100007
class Query:
def __init__(self, l, r, k):
self.l = l
self.r = r
self.k = k
def __lt__(self, other):
if self.l // sq == other.l // sq:
return self.r > other.r
return self.l // sq > other.l // sq
def add(g):
global res, b
if b[g] == 1: # 이 수가 1번 등장했었다면
res += 1
elif b[g] == 2: # 이 수가 2번 등장했었다면
res -= 1
b[g] += 1
def sub(g):
global res, b
if b[g] == 2: # 이 수가 2번 등장했었다면
res += 1
elif b[g] == 3: # 이 수가 3번 등장했었다면
res -= 1
b[g] -= 1
n, m = map(int, input().split())
li = list(map(int, input().split()))
sq = int(sqrt(n))
y = []
for _ in range(m):
q1, q2 = map(int, input().split())
y.append(Query(q1 - 1, q2 - 1, len(y)))
y.sort(reverse=True)
b = [0] * (mem * 11)
res = 0
s, e = 0, 0
add(li[0])
ans = [0] * m
for q in y:
ns, ne = q.l, q.r
for i in range(s, ns):
sub(li[i])
for i in range(s - 1, ns - 1, -1):
add(li[i])
for i in range(e + 1, ne + 1):
add(li[i])
for i in range(e, ne, -1):
sub(li[i])
s, e = ns, ne
ans[q.k] = res
for a in ans:
print(a)
#print(*ans, sep='\n')
