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()