# Fast IO (only use in integer input)



import os,io

input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline



# Fenwick Tree to Calculate Sum



N,Q = list(map(int,input().split()))



MaxLength = 2 ** 19

FenwickTree = []



CurLen = MaxLength

while CurLen != 0:

    FenwickTree.append([0] * CurLen)

    CurLen //= 2



Depth = len(FenwickTree)



def addElem(n,index): # add n to an element in index

    for j in range(Depth):

        FenwickTree[j][index] += n

        index //= 2



def firstNSum(n): # Return the sum of the first n elements (0 to n-1)

    nCpy = n

    summ = 0

    depthCur = 0

    while nCpy != 0:

        if nCpy % 2 != 0:

            summ += FenwickTree[depthCur][nCpy - 1]

        nCpy //= 2

        depthCur += 1

    return summ



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

firstLocColor = [-1] * N

ans = [-1] * Q

queries = []

for i in range(Q):

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

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

queries.sort(key = lambda x: x[1])

queryIndex = 0

for i in range(N):

    # Update the Fenwick tree to count ith element

    if firstLocColor[c[i] - 1] == -1:

        addElem(1,i)

        firstLocColor[c[i] - 1] = i

    else:

        addElem(-1,firstLocColor[c[i] - 1])

        addElem(1,i)

        firstLocColor[c[i] - 1] = i

    

    # get query

    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:

        if queries[queryIndex][1] - 1 == i:

            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(queries[queryIndex][0] - 1)

        queryIndex += 1



for elem in ans:

    print(elem)
# Fast IO (only use in integer input)



import os,io

input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline



# Fenwick Tree to Calculate Sum



N,Q = list(map(int,input().split()))



MaxLength = N

FenwickTree = []



CurLen = MaxLength

while CurLen != 0:

    FenwickTree.append([0] * CurLen)

    CurLen //= 2



Depth = len(FenwickTree)



def addElem(n,index): # add n to an element in index

    for j in range(Depth):

        if index < len(FenwickTree[j]):

            FenwickTree[j][index] += n

        index //= 2



def firstNSum(n): # Return the sum of the first n elements (0 to n-1)

    nCpy = n

    summ = 0

    depthCur = 0

    while nCpy != 0:

        if nCpy % 2 != 0:

            summ += FenwickTree[depthCur][nCpy - 1]

        nCpy //= 2

        depthCur += 1

    return summ



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

firstLocColor = [-1] * N

ans = [-1] * Q

queries = []

for i in range(Q):

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

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

queries.sort(key = lambda x: x[1])

queryIndex = 0

for i in range(N):

    # Update the Fenwick tree to count ith element

    if firstLocColor[c[i] - 1] == -1:

        addElem(1,i)

        firstLocColor[c[i] - 1] = i

    else:

        addElem(-1,firstLocColor[c[i] - 1])

        addElem(1,i)

        firstLocColor[c[i] - 1] = i

    

    # get query

    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:

        if queries[queryIndex][1] - 1 == i:

            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(queries[queryIndex][0] - 1)

        queryIndex += 1



for elem in ans:

    print(elem)
# Fast IO (only use in integer input)
import os, io

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
# Fenwick Tree to Calculate Sum
N, Q = list(map(int, input().split()))
MaxLength = 2**19
FenwickTree = []
CurLen = MaxLength
while CurLen != 0:
    FenwickTree.append([0] * CurLen)
    CurLen //= 2
Depth = len(FenwickTree)


def addElem(n, index):  # add n to an element in index
    for j in range(Depth):
        FenwickTree[j][index] += n
        index //= 2


def firstNSum(n):  # Return the sum of the first n elements (0 to n-1)
    nCpy = n
    summ = 0
    depthCur = 0
    while nCpy != 0:
        if nCpy % 2 != 0:
            summ += FenwickTree[depthCur][nCpy - 1]
        nCpy //= 2
        depthCur += 1
    return summ


c = list(map(int, input().split()))
firstLocColor = [-1] * N
ans = [-1] * Q
queries = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    queries.append((l, r, i))
queries.sort(key=lambda x: x[1])
queryIndex = 0
for i in range(N):
    # Update the Fenwick tree to count ith element
    if firstLocColor[c[i] - 1] == -1:
        addElem(1, i)
        firstLocColor[c[i] - 1] = i
    else:
        addElem(-1, firstLocColor[c[i] - 1])
        addElem(1, i)
        firstLocColor[c[i] - 1] = i
    # get query
    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:
        if queries[queryIndex][1] - 1 == i:
            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(
                queries[queryIndex][0] - 1
            )
        queryIndex += 1
for elem in ans:
    print(elem)

# Fast IO (only use in integer input)
import os, io

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
# Fenwick Tree to Calculate Sum
N, Q = list(map(int, input().split()))
MaxLength = N
FenwickTree = []
CurLen = MaxLength
while CurLen != 0:
    FenwickTree.append([0] * CurLen)
    CurLen //= 2
Depth = len(FenwickTree)


def addElem(n, index):  # add n to an element in index
    for j in range(Depth):
        if index < len(FenwickTree[j]):
            FenwickTree[j][index] += n
        index //= 2


def firstNSum(n):  # Return the sum of the first n elements (0 to n-1)
    nCpy = n
    summ = 0
    depthCur = 0
    while nCpy != 0:
        if nCpy % 2 != 0:
            summ += FenwickTree[depthCur][nCpy - 1]
        nCpy //= 2
        depthCur += 1
    return summ


c = list(map(int, input().split()))
firstLocColor = [-1] * N
ans = [-1] * Q
queries = []
for i in range(Q):
    l, r = list(map(int, input().split()))
    queries.append((l, r, i))
queries.sort(key=lambda x: x[1])
queryIndex = 0
for i in range(N):
    # Update the Fenwick tree to count ith element
    if firstLocColor[c[i] - 1] == -1:
        addElem(1, i)
        firstLocColor[c[i] - 1] = i
    else:
        addElem(-1, firstLocColor[c[i] - 1])
        addElem(1, i)
        firstLocColor[c[i] - 1] = i
    # get query
    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:
        if queries[queryIndex][1] - 1 == i:
            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(
                queries[queryIndex][0] - 1
            )
        queryIndex += 1
for elem in ans:
    print(elem)

-MaxLength = 2**19 +MaxLength = N -        FenwickTree[j][index] += n +        if index < len(FenwickTree[j]): +            FenwickTree[j][index] += n