"""

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

n,q=list(map(int,input().split()))

a=list(map(int,input().split()))

for i in range(n):a[i]-=1

queries=[[]for _ in range(n)]

for i in range(q):

  l,r=list(map(int,input().split()))

  l-=1

  r-=1

  queries[r].append((l,i))

lastAppeared=[0]*n

bit=[0]*(n+1)

ans=[0]*q

for i in range(n):

  x=lastAppeared[a[i]]+1

  while x<=n+1:

    bit[x-1]-=1

    x+=x&-x

  x=i+2

  while x<=n+1:

    bit[x-1]+=1

    x+=x&-x

  lastAppeared[a[i]]=i+1

  for l,ind in queries[i]:

    x=i+2

    while x:

      ans[ind]+=bit[x-1]

      x-=x&-x

    x=l+1

    while x:

      ans[ind]-=bit[x-1]

      x-=x&-x

print((*ans))

"""
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 = list(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 = list(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))

n, q = list(map(int, input().split()))
a = list(map(int, input().split()))
for i in range(n):
    a[i] -= 1
queries = [[] for _ in range(n)]
for i in range(q):
    l, r = list(map(int, input().split()))
    l -= 1
    r -= 1
    queries[r].append((l, i))
lastAppeared = [0] * n
bit = [0] * (n + 1)
ans = [0] * q
for i in range(n):
    x = lastAppeared[a[i]] + 1
    while x <= n + 1:
        bit[x - 1] -= 1
        x += x & -x
    x = i + 2
    while x <= n + 1:
        bit[x - 1] += 1
        x += x & -x
    lastAppeared[a[i]] = i + 1
    for l, ind in queries[i]:
        x = i + 2
        while x:
            ans[ind] += bit[x - 1]
            x -= x & -x
        x = l + 1
        while x:
            ans[ind] -= bit[x - 1]
            x -= x & -x
print((*ans))

-""" -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 - - -ans = [0] * q +for i in range(n): +    a[i] -= 1 -lastAppeared = [-1] * n -bitt = BinaryIndexedTree(n) -j = 0 +lastAppeared = [0] * n +bit = [0] * (n + 1) +ans = [0] * q -    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 +    x = lastAppeared[a[i]] + 1 +    while x <= n + 1: +        bit[x - 1] -= 1 +        x += x & -x +    x = i + 2 +    while x <= n + 1: +        bit[x - 1] += 1 +        x += x & -x +    lastAppeared[a[i]] = i + 1 -        ans[ind] = bitt.sum(l, i - 1) +        x = i + 2 +        while x: +            ans[ind] += bit[x - 1] +            x -= x & -x +        x = l + 1 +        while x: +            ans[ind] -= bit[x - 1] +            x -= x & -x