import sys

import numpy as np



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



Bsize = 700



def Mo_argsort(LR):

    L = LR[:, 0]

    R = LR[:, 1]

    key1 = L // Bsize

    key2 = np.where(key1 & 1, -R, R)

    key = (key1 << 32) + key2

    return np.argsort(key)



def main(A, LR):

    N = len(A)

    Q = len(LR)

    ind = Mo_argsort(LR)

    count = np.zeros(N + 1, np.int64)

    ans = 0



    def add(x):

        nonlocal ans

        if not count[x]:

            ans += 1

        count[x] += 1



    def rem(x):

        nonlocal ans

        count[x] -= 1

        if not count[x]:

            ans -= 1



    answers = np.empty(Q, np.int64)

    nl, nr = 0, 0

    for i in ind:

        l, r = LR[i]

        l -= 1

        # 区間 [l, r) に対する計算

        while nl > l:

            nl -= 1

            add(A[nl])

        while nr < r:

            add(A[nr])

            nr += 1

        while nl < l:

            rem(A[nl])

            nl += 1

        while nr > r:

            nr -= 1

            rem(A[nr])

        #  答を求めて ans[i] に格納する

        answers[i] = ans

    return answers



if sys.argv[-1] == 'ONLINE_JUDGE':

    import numba

    from numba.pycc import CC

    i4 = numba.int32

    i8 = numba.int64

    cc = CC('my_module')



    def cc_export(f, signature):

        cc.export(f.__name__, signature)(f)

        return numba.njit(f)



    Mo_argsort = cc_export(Mo_argsort, (i8[:,:],))

    main = cc_export(main, (i8[:], i8[:, :]))

    cc.compile()



from my_module import main



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

A = np.array(readline().split(), np.int64)

LR = np.array(read().split(), np.int64).reshape(Q, 2)



ans = main(A, LR)

print(('\n'.join(map(str, ans.tolist()))))
import sys

import numpy as np



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



Bsize = 1000



def Mo_argsort(LR):

    L = LR[:, 0]

    R = LR[:, 1]

    key1 = L // Bsize

    key2 = np.where(key1 & 1, -R, R)

    key = (key1 << 32) + key2

    return np.argsort(key)



def main(A, LR):

    N = len(A)

    Q = len(LR)

    ind = Mo_argsort(LR)

    count = np.zeros(N + 1, np.int64)

    ans = 0



    def add(x):

        nonlocal ans

        if not count[x]:

            ans += 1

        count[x] += 1



    def rem(x):

        nonlocal ans

        count[x] -= 1

        if not count[x]:

            ans -= 1



    answers = np.empty(Q, np.int64)

    nl, nr = 0, 0

    for i in ind:

        l, r = LR[i]

        l -= 1

        # 区間 [l, r) に対する計算

        while nl > l:

            nl -= 1

            add(A[nl])

        while nr < r:

            add(A[nr])

            nr += 1

        while nl < l:

            rem(A[nl])

            nl += 1

        while nr > r:

            nr -= 1

            rem(A[nr])

        #  答を求めて ans[i] に格納する

        answers[i] = ans

    return answers



if sys.argv[-1] == 'ONLINE_JUDGE':

    import numba

    from numba.pycc import CC

    i4 = numba.int32

    i8 = numba.int64

    cc = CC('my_module')



    def cc_export(f, signature):

        cc.export(f.__name__, signature)(f)

        return numba.njit(f)



    Mo_argsort = cc_export(Mo_argsort, (i8[:,:],))

    main = cc_export(main, (i8[:], i8[:, :]))

    cc.compile()



from my_module import main



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

A = np.array(readline().split(), np.int64)

LR = np.array(read().split(), np.int64).reshape(Q, 2)



ans = main(A, LR)

print(('\n'.join(map(str, ans.tolist()))))

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
Bsize = 700


def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)


def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int64)
    ans = 0

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int64)
    nl, nr = 0, 0
    for i in ind:
        l, r = LR[i]
        l -= 1
        # 区間 [l, r) に対する計算
        while nl > l:
            nl -= 1
            add(A[nl])
        while nr < r:
            add(A[nr])
            nr += 1
        while nl < l:
            rem(A[nl])
            nl += 1
        while nr > r:
            nr -= 1
            rem(A[nr])
        #  答を求めて ans[i] に格納する
        answers[i] = ans
    return answers


if sys.argv[-1] == "ONLINE_JUDGE":
    import numba
    from numba.pycc import CC

    i4 = numba.int32
    i8 = numba.int64
    cc = CC("my_module")

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    Mo_argsort = cc_export(Mo_argsort, (i8[:, :],))
    main = cc_export(main, (i8[:], i8[:, :]))
    cc.compile()
from my_module import main

N, Q = list(map(int, readline().split()))
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q, 2)
ans = main(A, LR)
print(("\n".join(map(str, ans.tolist()))))

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
Bsize = 1000


def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)


def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int64)
    ans = 0

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int64)
    nl, nr = 0, 0
    for i in ind:
        l, r = LR[i]
        l -= 1
        # 区間 [l, r) に対する計算
        while nl > l:
            nl -= 1
            add(A[nl])
        while nr < r:
            add(A[nr])
            nr += 1
        while nl < l:
            rem(A[nl])
            nl += 1
        while nr > r:
            nr -= 1
            rem(A[nr])
        #  答を求めて ans[i] に格納する
        answers[i] = ans
    return answers


if sys.argv[-1] == "ONLINE_JUDGE":
    import numba
    from numba.pycc import CC

    i4 = numba.int32
    i8 = numba.int64
    cc = CC("my_module")

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    Mo_argsort = cc_export(Mo_argsort, (i8[:, :],))
    main = cc_export(main, (i8[:], i8[:, :]))
    cc.compile()
from my_module import main

N, Q = list(map(int, readline().split()))
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q, 2)
ans = main(A, LR)
print(("\n".join(map(str, ans.tolist()))))

-Bsize = 700 +Bsize = 1000