def main():

  n,q,*x=list(map(int,open(0).read().split()))

  a=x[:n]

  queries=[[]for _ in[0]*n]

  for i in range(q):

    l,r=x[n+i*2],x[n+i*2+1]

    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]+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]-1]=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))



if __name__ == "__main__":

  main()
import sys

input = sys.stdin.buffer.readline

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

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

queries=[[]for _ in[0]*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]+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]-1]=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))

def main():
    n, q, *x = list(map(int, open(0).read().split()))
    a = x[:n]
    queries = [[] for _ in [0] * n]
    for i in range(q):
        l, r = x[n + i * 2], x[n + i * 2 + 1]
        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] + 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] - 1] = 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))


if __name__ == "__main__":
    main()

import sys

input = sys.stdin.buffer.readline
n, q = list(map(int, input().split()))
a = list(map(int, input().split()))
queries = [[] for _ in [0] * 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] + 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] - 1] = 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))

-def main(): -    n, q, *x = list(map(int, open(0).read().split())) -    a = x[:n] -    queries = [[] for _ in [0] * n] -    for i in range(q): -        l, r = x[n + i * 2], x[n + i * 2 + 1] -        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] + 1 -        while x <= n + 1: -            bit[x - 1] -= 1 -            x += x & -x +import sys + +input = sys.stdin.buffer.readline +n, q = list(map(int, input().split())) +a = list(map(int, input().split())) +queries = [[] for _ in [0] * 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] + 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] - 1] = i + 1 +    for l, ind in queries[i]: -        while x <= n + 1: -            bit[x - 1] += 1 -            x += x & -x -        lastAppeared[a[i] - 1] = 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)) - - -if __name__ == "__main__": -    main() +        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))