from sys import stdin,stdout
from collections import *
from math import *
st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")
mod=1000000007
INF=float('inf')
d={}
length=0
def ADD(x):
global length
if x not in d:
length+=1
d[x]=1
else:
d[x]+=1
def REMOVE(x):
global length
if d[x]==1:
length-=1
d.pop(x)
else:
d[x]-=1
def solve():
n,q=mp()
l=li()
query=[li()+[i] for i in range(q)]
query.sort(key=lambda x:(x[0],x[1]))
curL,curR=0,-1
ans=[0 for i in range(q)]
for Q in query:
left,right,ind=Q
left-=1
right-=1
while curL>left:
curL-=1
ADD(l[curL])
while curR<right:
curR+=1
ADD(l[curR])
while curL<left:
REMOVE(l[curL])
curL+=1
while curR>right:
REMOVE(l[curR])
curR-=1
ans[ind]=length
print('\n'.join(map(str,ans)))
for _ in range(1):
solve()
ZnJvbSBzeXMgIGltcG9ydCBzdGRpbixzdGRvdXQKZnJvbSBjb2xsZWN0aW9ucyAgaW1wb3J0ICoKZnJvbSBtYXRoIGltcG9ydCAqCnN0PWxhbWJkYTpsaXN0KHN0ZGluLnJlYWRsaW5lKCkuc3RyaXAoKSkKbGk9bGFtYmRhOmxpc3QobWFwKGludCxzdGRpbi5yZWFkbGluZSgpLnNwbGl0KCkpKQptcD1sYW1iZGE6bWFwKGludCxzdGRpbi5yZWFkbGluZSgpLnNwbGl0KCkpCmlucD1sYW1iZGE6aW50KHN0ZGluLnJlYWRsaW5lKCkpCnByPWxhbWJkYSBuOiBzdGRvdXQud3JpdGUoc3RyKG4pKyJcbiIpCgptb2Q9MTAwMDAwMDAwNwpJTkY9ZmxvYXQoJ2luZicpCmQ9e30KCmxlbmd0aD0wCgpkZWYgQUREKHgpOgogICAgZ2xvYmFsIGxlbmd0aAogICAgaWYgeCBub3QgaW4gZDoKICAgICAgICBsZW5ndGgrPTEKICAgICAgICBkW3hdPTEKICAgIGVsc2U6CiAgICAgICAgZFt4XSs9MQogICAgICAgIApkZWYgUkVNT1ZFKHgpOgogICAgZ2xvYmFsIGxlbmd0aAogICAgaWYgZFt4XT09MToKICAgICAgICBsZW5ndGgtPTEKICAgICAgICBkLnBvcCh4KQogICAgZWxzZToKICAgICAgICBkW3hdLT0xCiAgICAKICAgIAoKZGVmIHNvbHZlKCk6CiAgICBuLHE9bXAoKQogICAgbD1saSgpCiAgICBxdWVyeT1bbGkoKStbaV0gZm9yIGkgaW4gcmFuZ2UocSldCiAgICBxdWVyeS5zb3J0KGtleT1sYW1iZGEgeDooeFswXSx4WzFdKSkKICAgIGN1ckwsY3VyUj0wLC0xCiAgICBhbnM9WzAgZm9yIGkgaW4gcmFuZ2UocSldCiAgICBmb3IgUSBpbiBxdWVyeToKICAgICAgICBsZWZ0LHJpZ2h0LGluZD1RCiAgICAgICAgbGVmdC09MQogICAgICAgIHJpZ2h0LT0xCiAgICAgICAgCiAgICAgICAgd2hpbGUgY3VyTD5sZWZ0OgogICAgICAgICAgICBjdXJMLT0xCiAgICAgICAgICAgIEFERChsW2N1ckxdKQogICAgICAgIAogICAgICAgIHdoaWxlIGN1clI8cmlnaHQ6CiAgICAgICAgICAgIGN1clIrPTEKICAgICAgICAgICAgQUREKGxbY3VyUl0pCiAgICAKICAgICAgICB3aGlsZSBjdXJMPGxlZnQ6CiAgICAgICAgICAgIFJFTU9WRShsW2N1ckxdKQogICAgICAgICAgICBjdXJMKz0xCiAgICAgICAgICAgIAogICAgICAgIHdoaWxlIGN1clI+cmlnaHQ6CiAgICAgICAgICAgIFJFTU9WRShsW2N1clJdKQogICAgICAgICAgICBjdXJSLT0xCiAgICAgICAgCiAgICAgICAgYW5zW2luZF09bGVuZ3RoCiAgICAgICAgCiAgICBwcmludCgnXG4nLmpvaW4obWFwKHN0cixhbnMpKSkKICAgICAgICAKICAgICAgICAgICAgCiAgICAKZm9yIF8gaW4gcmFuZ2UoMSk6CiAgICBzb2x2ZSgpCg==