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))

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))

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))

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))

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