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)]
    P=int(n**0.5)
    query.sort(key=lambda x:(x[0]//P,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()
 

ZnJvbSBzeXMgIGltcG9ydCBzdGRpbixzdGRvdXQKZnJvbSBjb2xsZWN0aW9ucyAgaW1wb3J0ICoKZnJvbSBtYXRoIGltcG9ydCAqCnN0PWxhbWJkYTpsaXN0KHN0ZGluLnJlYWRsaW5lKCkuc3RyaXAoKSkKbGk9bGFtYmRhOmxpc3QobWFwKGludCxzdGRpbi5yZWFkbGluZSgpLnNwbGl0KCkpKQptcD1sYW1iZGE6bWFwKGludCxzdGRpbi5yZWFkbGluZSgpLnNwbGl0KCkpCmlucD1sYW1iZGE6aW50KHN0ZGluLnJlYWRsaW5lKCkpCnByPWxhbWJkYSBuOiBzdGRvdXQud3JpdGUoc3RyKG4pKyJcbiIpCgptb2Q9MTAwMDAwMDAwNwpJTkY9ZmxvYXQoJ2luZicpCmQ9e30KCmxlbmd0aD0wCgpkZWYgQUREKHgpOgogICAgZ2xvYmFsIGxlbmd0aAogICAgaWYgeCBub3QgaW4gZDoKICAgICAgICBsZW5ndGgrPTEKICAgICAgICBkW3hdPTEKICAgIGVsc2U6CiAgICAgICAgZFt4XSs9MQogICAgICAgIApkZWYgUkVNT1ZFKHgpOgogICAgZ2xvYmFsIGxlbmd0aAogICAgaWYgZFt4XT09MToKICAgICAgICBsZW5ndGgtPTEKICAgICAgICBkLnBvcCh4KQogICAgZWxzZToKICAgICAgICBkW3hdLT0xCiAgICAKICAgIAoKZGVmIHNvbHZlKCk6CiAgICBuLHE9bXAoKQogICAgbD1saSgpCiAgICBxdWVyeT1bbGkoKStbaV0gZm9yIGkgaW4gcmFuZ2UocSldCiAgICBQPWludChuKiowLjUpCiAgICBxdWVyeS5zb3J0KGtleT1sYW1iZGEgeDooeFswXS8vUCx4WzFdKSkKICAgIGN1ckwsY3VyUj0wLC0xCiAgICBhbnM9WzAgZm9yIGkgaW4gcmFuZ2UocSldCiAgICBmb3IgUSBpbiBxdWVyeToKICAgICAgICBsZWZ0LHJpZ2h0LGluZD1RCiAgICAgICAgbGVmdC09MQogICAgICAgIHJpZ2h0LT0xCiAgICAgICAgCiAgICAgICAgd2hpbGUgY3VyTD5sZWZ0OgogICAgICAgICAgICBjdXJMLT0xCiAgICAgICAgICAgIEFERChsW2N1ckxdKQogICAgICAgIAogICAgICAgIHdoaWxlIGN1clI8cmlnaHQ6CiAgICAgICAgICAgIGN1clIrPTEKICAgICAgICAgICAgQUREKGxbY3VyUl0pCiAgICAKICAgICAgICB3aGlsZSBjdXJMPGxlZnQ6CiAgICAgICAgICAgIFJFTU9WRShsW2N1ckxdKQogICAgICAgICAgICBjdXJMKz0xCiAgICAgICAgICAgIAogICAgICAgIHdoaWxlIGN1clI+cmlnaHQ6CiAgICAgICAgICAgIFJFTU9WRShsW2N1clJdKQogICAgICAgICAgICBjdXJSLT0xCiAgICAgICAgCiAgICAgICAgYW5zW2luZF09bGVuZ3RoCiAgICAgICAgCiAgICBwcmludCgnXG4nLmpvaW4obWFwKHN0cixhbnMpKSkKICAgICAgICAKICAgICAgICAgICAgCiAgICAKZm9yIF8gaW4gcmFuZ2UoMSk6CiAgICBzb2x2ZSgpCg==

MTAgMTAKMiA1IDYgNSAyIDEgNyA5IDcgMgo1IDUKMiA0CjYgNwoyIDIKNyA4CjcgOQoxIDgKNiA5CjggMTAKNiA4Cg==

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8