import sys

import numpy as np

import numba

from numba import njit

from numba.types import Omitted

i4 = numba.int32

i8 = numba.int64



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



@njit((i8[:], i8), cache=True)

def get_sum(bit, i):

    s = 0

    while i:

        s += bit[i]

        i -= i & -i

    return s





@njit((i8[:], i8, i8), cache=True)

def add(bit, i, x):

    while i < len(bit):

        bit[i] += x

        i += i & -i



@njit((i8[:], i8[:]), cache=True)

def main(A, LR):

    N = len(A)

    L, R = LR[::2], LR[1::2]

    Q = len(L)

    query_order = np.argsort(R)

    L, R = L[query_order], R[query_order]

    ind = np.searchsorted(R, np.arange(N + 2))

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

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

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

    for r in range(1, N + 1):

        a = A[r - 1]

        p = right_end[a]

        if p:

            add(bit, p, -1)

        right_end[a] = r

        add(bit, r, 1)

        for i in range(ind[r], ind[r + 1]):

            l, r, i = L[i], R[i], query_order[i]

            answers[i] = get_sum(bit, r) - get_sum(bit, l - 1)

    return answers



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

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

LR = np.array(read().split(), np.int64)



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



def get_sum(bit, i):

    s = 0

    while i:

        s += bit[i]

        i -= i & -i

    return s



def add(bit, i, x):

    while i < len(bit):

        bit[i] += x

        i += i & -i



def main(A, LR):

    N = len(A)

    L, R = LR[::2], LR[1::2]

    Q = len(L)

    query_order = np.argsort(R)

    L, R = L[query_order], R[query_order]

    ind = np.searchsorted(R, np.arange(N + 2))

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

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

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

    for r in range(1, N + 1):

        a = A[r - 1]

        p = right_end[a]

        if p:

            add(bit, p, -1)

        right_end[a] = r

        add(bit, r, 1)

        for i in range(ind[r], ind[r + 1]):

            l, r, i = L[i], R[i], query_order[i]

            answers[i] = get_sum(bit, r) - get_sum(bit, l - 1)

    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)



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

    add = cc_export(add, (i8[:], i8, 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)



ans = main(A, LR)

print(('\n'.join(map(str, ans.tolist()))))
import sys
import numpy as np
import numba
from numba import njit
from numba.types import Omitted

i4 = numba.int32
i8 = numba.int64
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8[:]), cache=True)
def main(A, LR):
    N = len(A)
    L, R = LR[::2], LR[1::2]
    Q = len(L)
    query_order = np.argsort(R)
    L, R = L[query_order], R[query_order]
    ind = np.searchsorted(R, np.arange(N + 2))
    right_end = np.zeros(N + 1, np.int64)
    bit = np.zeros(N + 1, np.int64)
    answers = np.empty(Q, np.int64)
    for r in range(1, N + 1):
        a = A[r - 1]
        p = right_end[a]
        if p:
            add(bit, p, -1)
        right_end[a] = r
        add(bit, r, 1)
        for i in range(ind[r], ind[r + 1]):
            l, r, i = L[i], R[i], query_order[i]
            answers[i] = get_sum(bit, r) - get_sum(bit, l - 1)
    return answers


N, Q = list(map(int, readline().split()))
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64)
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


def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


def main(A, LR):
    N = len(A)
    L, R = LR[::2], LR[1::2]
    Q = len(L)
    query_order = np.argsort(R)
    L, R = L[query_order], R[query_order]
    ind = np.searchsorted(R, np.arange(N + 2))
    right_end = np.zeros(N + 1, np.int64)
    bit = np.zeros(N + 1, np.int64)
    answers = np.empty(Q, np.int64)
    for r in range(1, N + 1):
        a = A[r - 1]
        p = right_end[a]
        if p:
            add(bit, p, -1)
        right_end[a] = r
        add(bit, r, 1)
        for i in range(ind[r], ind[r + 1]):
            l, r, i = L[i], R[i], query_order[i]
            answers[i] = get_sum(bit, r) - get_sum(bit, l - 1)
    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)

    get_sum = cc_export(get_sum, (i8[:], i8))
    add = cc_export(add, (i8[:], i8, 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)
ans = main(A, LR)
print(("\n".join(map(str, ans.tolist()))))

-import numba -from numba import njit -from numba.types import Omitted -i4 = numba.int32 -i8 = numba.int64 -@njit((i8[:], i8), cache=True) -@njit((i8[:], i8, i8), cache=True) -@njit((i8[:], i8[:]), cache=True) +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) + +    get_sum = cc_export(get_sum, (i8[:], i8)) +    add = cc_export(add, (i8[:], i8, i8)) +    main = cc_export(main, (i8[:], i8[:])) +    cc.compile() +from my_module import main +