"""
O_______________________________________________________________________________________________________________O
*                                                                                                               *
*                        xxxxx                                                                                  *
*                       xxxxxxx                                                 xxxxxxxxxxxxxxxxx               *
*                      xxxxxxxxx                                           xxxxxxxxxx      xxxxxxxxxxx          *
*                     xxxxx xxxxx                                      xxxxx                     xxxxxxxxxx     *
*                    xxxxx   xxxxx                                  xxxxx                             xxxxxxx   *
*                   xxxxx     xxxxx                               xxxxx                                         *
*                  xxxxx       xxxxx                             xxxxx                                          *
*                 xxxxx         xxxxx                           xxxxx                                           *
*                xxxxx           xxxxx                          xxxxx                                           *
*               xxxxx             xxxxx                        xxxxx                                            *
*              xxxxx               xxxxx                       xxxxx                                            *
*             xxxxx                 xxxxx                     xxxxx                                             *
*            xxxxxxxxxxxxxxxxxxxxxxxxxxxxx                    xxxxx                                             *
*           xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx                   xxxxx                                             *
*          xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx                   xxxxx                                            *
*         xxxxx                         xxxxx                  xxxxx                                            *
*        xxxxx                           xxxxx                  xxxxx                                           *
*       xxxxx                             xxxxx                 xxxxx                                           *
*      xxxxx                               xxxxx                 xxxxx                                          *
*     xxxxx                                 xxxxx                 xxxxx                                         *
*    xxxxx                                   xxxxx                  xxxxx                             xxxxxxx   *
*   xxxxx                                     xxxxx                    xxxxx                     xxxxxxxxxx     *
*  xxxxx                                       xxxxx                       xxxxxxxxxx      xxxxxxxxxxx          *
* xxxxx                                         xxxxx                           xxxxxxxxxxxxxxxxx               *
*                                                                                                               *
O_______________________________________________________________________________________________________________O
"""
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*q
queries=[[]for _ in range(n)]
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[-1]*n
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]-1]!=-1:
    bitt.add(lastAppeared[a[i]-1],-1)
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  for l,ind in queries[i]:
    ans[ind]=bitt.sum(l,i-1)
print(*ans)


Measured memory_bytes: 207552