### BUGGY CODE ###

import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

n,q=map(int,input().split())
A=list(map(int,input().split()))
Q=[]
for i in range(q):
    a,b=map(int,input().split())
    a-=1 ; b-=1
    Q.append([i,a,b])
Q=sorted(Q, key=lambda x: x[2])
ANS=[-1]*q

A=[i-1 for i in A]

C=[-1]*n #その色の一番右の球はどこ
G=[0]*n #右球があるところに1


left=Q[0][1] ; right=Q[0][2]
for i in range(right,-1,-1):
    if C[A[i]]==-1:
        C[A[i]]=i
for i in C:
    if i==-1 : continue
    G[i]=1

ruiG=[G[0]]*n
for i in range(n-1):
    ruiG[i+1]=ruiG[i]+G[i+1]

ANS[Q[0][0]]=ruiG[right]-ruiG[left-1] if left!=0 else ruiG[right]

# print("A",A)
# print("C",C)
# print("G",G)
# print("ruiG",ruiG)
# print("ANS",ANS)


for l in Q[1:]:
    num=l[0]
    newleft,newright=l[1],l[2] ; #print(left,right,newleft,newright)
    for i in range(right+1,newright+1):
        if C[A[i]]==-1:
            G[i]=1 #未発見の色
            C[A[i]]=i
        else:
            G[C[A[i]]]=0 #既発見の色、更新
            C[A[i]]=i
            G[i]=1 #発見された場所に1
    #print("C",C)
    #print("G",G)
    # print("ruiG",ruiG)
    ANS[num]= sum(G[newleft:newright+1]) 
    # print("ans",sum(G[newleft:newright+1]))
    right,left=newright,newleft
for i in ANS:
    print(i)
    

    



### FIXED CODE ###

import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
class BIT:
    def __init__(self,n):
        self.n=n
        self.data= [0]*(n+1) #これがBIT
        self.el= [0]*(n+1) #これが元データ
    def sum(self,i):  #iまでの和
        s=0
        while i>0:
            s+=self.data[i]
            i-= i&(-i)
        return s
    def add(self,i,x):  #iにxを足す(x<0)
        self.el[i]+=x
        while i<= self.n:
            self.data[i]+= x
            i+= i&-i
    def get(self,i,j=None):  #iからjまでの和、iだけなら普通の要素iを取得(いる？)
        if j is None:
            return self.el[i]
        return self.sum(j)-self.sum(i)
    

n,q=map(int,input().split())
C=list(map(int,input().split()))
C=[i-1 for i in C]  #球の純粋配置
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    l-=1;r-=1
    Q.append([i,l,r])
Q=sorted(Q, key=lambda x:x[2]) 
ANS=[-1]*q

B=BIT(n)
YOI=[-1]*n #色iの良い球の位置
# for i in range(Q[0][2],-1,-1):
#     if YOI[i]==-1:
#         YOI[C[i]]=i
#         B.add(i+1,1)
# 
# 
# ANS[Q[0][0]]= B.sum(Q[0][2]+1)- B.sum(Q[0][1])
# left=Q[0][1]; right=Q[0][2]
#print(B.data)
right=-1
for l in Q:
    newleft,newright=l[1],l[2]
    for i in range(newright,right,-1):
        if YOI[C[i]]==-1: #新種の色
            YOI[C[i]]=i
            B.add(i+1, 1)
        elif YOI[C[i]]>i:
            continue
        else:
            B.add(YOI[C[i]]+1, -1)
            YOI[C[i]]=i
            B.add(i+1, 1)
    ANS[l[0]]= B.sum(newright+1)- B.sum(newleft)
    right=newright
    #print(B.data)
for i in ANS:
    print(i)