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

C = [0] + list(map(int, input().split()))

D = [-1]*(n+1)

A = [0]*q

U = 10**6

LR = tuple(tuple(map(int, input().split())) for _ in range(q))

W = sorted(r*U+i for i, (l, r) in enumerate(LR))

B = [0]*(1<<n.bit_length())

def add(i, a):

  while i <= n:

    B[i] += a

    i += i & -i

def acc(i):

  res = 0

  while i:

    res += B[i]

    i -= i & -i

  return res

temp = 1

for w in W:

  r, i = divmod(w, U)

  while temp <= r:

    c = C[temp]

    add(temp, 1)

    if D[c] != -1:

      add(D[c], -1)

    D[c] = temp

    temp += 1

  l = LR[i][0]

  A[i] = acc(r) - acc(l-1)

print(*A, sep="\n")

import sys

input = sys.stdin.readline



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

C = [0] + list(map(int, input().split()))

D = [-1]*(n+1)

A = [0]*q

U = 10**6

LR = tuple(tuple(map(int, input().split())) for _ in range(q))

W = sorted(r*U+i for i, (l, r) in enumerate(LR))

B = [0]*(1<<n.bit_length())

def add(i, a):

  while i <= n:

    B[i] += a

    i += i & -i

def acc(i):

  res = 0

  while i:

    res += B[i]

    i -= i & -i

  return res

temp = 1

for w in W:

  r, i = divmod(w, U)

  while temp <= r:

    c = C[temp]

    add(temp, 1)

    if D[c] != -1:

      add(D[c], -1)

    D[c] = temp

    temp += 1

  l = LR[i][0]

  A[i] = acc(r) - acc(l-1)

print(*A, sep="\n")

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1] * (n + 1)
A = [0] * q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r * U + i for i, (l, r) in enumerate(LR))
B = [0] * (1 << n.bit_length())


def add(i, a):
    while i <= n:
        B[i] += a
        i += i & -i


def acc(i):
    res = 0
    while i:
        res += B[i]
        i -= i & -i
    return res


temp = 1
for w in W:
    r, i = divmod(w, U)
    while temp <= r:
        c = C[temp]
        add(temp, 1)
        if D[c] != -1:
            add(D[c], -1)
        D[c] = temp
        temp += 1
    l = LR[i][0]
    A[i] = acc(r) - acc(l - 1)
print(*A, sep="\n")

import sys

input = sys.stdin.readline
n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1] * (n + 1)
A = [0] * q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r * U + i for i, (l, r) in enumerate(LR))
B = [0] * (1 << n.bit_length())


def add(i, a):
    while i <= n:
        B[i] += a
        i += i & -i


def acc(i):
    res = 0
    while i:
        res += B[i]
        i -= i & -i
    return res


temp = 1
for w in W:
    r, i = divmod(w, U)
    while temp <= r:
        c = C[temp]
        add(temp, 1)
        if D[c] != -1:
            add(D[c], -1)
        D[c] = temp
        temp += 1
    l = LR[i][0]
    A[i] = acc(r) - acc(l - 1)
print(*A, sep="\n")

+import sys + +input = sys.stdin.readline