import sys

import numpy as np



read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



Bsize = 1333



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

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
Bsize = 1333


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
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 numba +from numba import njit +from numba.types import Omitted +i4 = numba.int32 +i8 = numba.int64 -Bsize = 1333 -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) +@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) -    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 - +    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) -    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 +    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) -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 - -LR = np.array(read().split(), np.int64).reshape(Q, 2) +LR = np.array(read().split(), np.int64)