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

mae=[2**i for i in range(21)]  #10**6 = 2**19.93
import bisect as bi
ookisa= mae[ bi.bisect_left(mae,n) ]
BIT=[0]*(ookisa+1)
#BIT[0]は使用しない(1-indexedにしたいので)
# print(BIT)

def bsum(i):
    ans=0
    while i>0:
        ans+=BIT[i]
        i -= i & (-i)
    return ans

def badd(i,x):
    while i<=len(BIT):
        BIT[i]+=x
        i += i & (-i)
def bmenos(i):
    while i<=len(BIT):
        BIT[i]-=1
        i += i&(-i)

# for i in range(1,len(A)+1): #配列をぶち込む
#     badd(i,A[i-1])

# print(BIT)

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
    badd(i+1, 1) #1-indexed


# print("A",A)
# print("C",C)
# print("G",G)
# print("ruiG",ruiG)
# print("ANS",ANS)
#print(BIT)
ANS[Q[0][0]]=bsum(right+1)-bsum(left)  #0問目

for l in Q[1:]:
    newleft=l[1] ; newright=l[2]
    for i in range(newright, right,-1):
        if C[A[i]] ==-1: #まだ発見してない色
            C[A[i]] = i
            badd(i+1,1)
        else:
            bmenos(C[A[i]]+1)
            C[A[i]] =i
            badd(i+1,1)
    ANS[l[0]]= bsum(newright+1)-bsum(newleft)
    left=newleft ; right=newright
    #print(BIT, bsum(newright+1)-bsum(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)