import os

import sys



import numpy as np





def solve(inp):

    def bit_add(arr, n, i, x):

        while i <= n:

            arr[i] += x

            i += i & -i



    def bit_sum(arr, i):

        result = 0

        while i > 0:

            result += arr[i]

            i ^= i & -i

        return result



    n = inp[0]

    q = inp[1]

    ccc = inp[2:2 + n]

    lll = inp[2 + n::2] - 1

    rrr = inp[3 + n::2] - 1



    just_left = {}

    segments = []

    for i in range(n):

        c = ccc[i]

        if c in just_left:

            segments.append((i, 0, just_left[c], 0))

        just_left[c] = i



    for i in range(q):

        segments.append((rrr[i], 1, lll[i], i))



    segments.sort()

    bit = np.zeros(n + 2, dtype=np.int64)

    ans = np.zeros(q, dtype=np.int64)



    for r, tp, l, i in segments:

        if tp == 0:

            bit_add(bit, n + 2, l + 2, 1)

        else:

            base = r - l + 1

            ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))

    return ans





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

    from numba.pycc import CC



    cc = CC('my_module')

    cc.export('solve', '(i8[:],)')(solve)

    cc.compile()

    exit()



if os.name == 'posix':

    # noinspection PyUnresolvedReferences

    from my_module import solve

else:

    from numba import njit



    solve = njit('(i8[:],)', cache=True)(solve)

    print('compiled', file=sys.stderr)



inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')

ans = solve(inp)

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

import os

import sys



import numpy as np





def solve(inp):

    def bit_add(arr, n, i, x):

        while i <= n:

            arr[i] += x

            i += i & -i



    def bit_sum(arr, i):

        result = 0

        while i > 0:

            result += arr[i]

            i ^= i & -i

        return result



    n = inp[0]

    q = inp[1]

    ccc = inp[2:2 + n] - 1

    lll = inp[2 + n::2] - 1

    rrr = inp[3 + n::2] - 1



    bit = np.zeros(n + 2, dtype=np.int64)

    appeared = np.full(n, -1, dtype=np.int64)

    ans = np.zeros(q, dtype=np.int64)



    p = 0

    for i in np.argsort(rrr):

        while p <= rrr[i]:

            c = ccc[p]

            before_appeared = appeared[c]

            if before_appeared != -1:

                bit_add(bit, n + 2, before_appeared + 2, -1)

            bit_add(bit, n + 2, p + 2, 1)

            appeared[c] = p

            p += 1



        ans[i] = bit_sum(bit, rrr[i] + 2) - bit_sum(bit, lll[i] + 1)



    return ans





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

    from numba.pycc import CC



    cc = CC('my_module')

    cc.export('solve', '(i8[:],)')(solve)

    cc.compile()

    exit()



if os.name == 'posix':

    # noinspection PyUnresolvedReferences

    from my_module import solve

else:

    from numba import njit



    solve = njit('(i8[:],)', cache=True)(solve)

    print('compiled', file=sys.stderr)



inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')

ans = solve(inp)

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

import os
import sys
import numpy as np


def solve(inp):
    def bit_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def bit_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    n = inp[0]
    q = inp[1]
    ccc = inp[2 : 2 + n]
    lll = inp[2 + n :: 2] - 1
    rrr = inp[3 + n :: 2] - 1
    just_left = {}
    segments = []
    for i in range(n):
        c = ccc[i]
        if c in just_left:
            segments.append((i, 0, just_left[c], 0))
        just_left[c] = i
    for i in range(q):
        segments.append((rrr[i], 1, lll[i], i))
    segments.sort()
    bit = np.zeros(n + 2, dtype=np.int64)
    ans = np.zeros(q, dtype=np.int64)
    for r, tp, l, i in segments:
        if tp == 0:
            bit_add(bit, n + 2, l + 2, 1)
        else:
            base = r - l + 1
            ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))
    return ans


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

    cc = CC("my_module")
    cc.export("solve", "(i8[:],)")(solve)
    cc.compile()
    exit()
if os.name == "posix":
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit("(i8[:],)", cache=True)(solve)
    print("compiled", file=sys.stderr)
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=" ")
ans = solve(inp)
print("\n".join(map(str, ans)))

import os
import sys
import numpy as np


def solve(inp):
    def bit_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def bit_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    n = inp[0]
    q = inp[1]
    ccc = inp[2 : 2 + n] - 1
    lll = inp[2 + n :: 2] - 1
    rrr = inp[3 + n :: 2] - 1
    bit = np.zeros(n + 2, dtype=np.int64)
    appeared = np.full(n, -1, dtype=np.int64)
    ans = np.zeros(q, dtype=np.int64)
    p = 0
    for i in np.argsort(rrr):
        while p <= rrr[i]:
            c = ccc[p]
            before_appeared = appeared[c]
            if before_appeared != -1:
                bit_add(bit, n + 2, before_appeared + 2, -1)
            bit_add(bit, n + 2, p + 2, 1)
            appeared[c] = p
            p += 1
        ans[i] = bit_sum(bit, rrr[i] + 2) - bit_sum(bit, lll[i] + 1)
    return ans


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

    cc = CC("my_module")
    cc.export("solve", "(i8[:],)")(solve)
    cc.compile()
    exit()
if os.name == "posix":
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit("(i8[:],)", cache=True)(solve)
    print("compiled", file=sys.stderr)
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=" ")
ans = solve(inp)
print("\n".join(map(str, ans)))

-    ccc = inp[2 : 2 + n] +    ccc = inp[2 : 2 + n] - 1 -    just_left = {} -    segments = [] -    for i in range(n): -        c = ccc[i] -        if c in just_left: -            segments.append((i, 0, just_left[c], 0)) -        just_left[c] = i -    for i in range(q): -        segments.append((rrr[i], 1, lll[i], i)) -    segments.sort() +    appeared = np.full(n, -1, dtype=np.int64) -    for r, tp, l, i in segments: -        if tp == 0: -            bit_add(bit, n + 2, l + 2, 1) -        else: -            base = r - l + 1 -            ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1)) +    p = 0 +    for i in np.argsort(rrr): +        while p <= rrr[i]: +            c = ccc[p] +            before_appeared = appeared[c] +            if before_appeared != -1: +                bit_add(bit, n + 2, before_appeared + 2, -1) +            bit_add(bit, n + 2, p + 2, 1) +            appeared[c] = p +            p += 1 +        ans[i] = bit_sum(bit, rrr[i] + 2) - bit_sum(bit, lll[i] + 1)