### BUGGY CODE ###

import sys
import numpy as np
def proc(C, L, R, Order, N, Q):
    pl = pr = 0
    ans = 0
    A = np.zeros(N+1, dtype=np.int32)
    Ans = np.zeros(Q, dtype=np.int32)
    for idx_LR in Order:
        l = L[idx_LR]
        r = R[idx_LR]
        while pr < r:
            pr += 1
            c = C[pr]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pl > l:
            pl -= 1
            c = C[pl]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pr > r:
            c = C[pr]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pr -= 1
        while pl < l:
            c = C[pl]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pl += 1
        Ans[idx_LR] = ans
    return Ans

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
    build = cc_export(proc, "i4[:](i4[:],u4[:],u4[:],i8[:],i4,i4)")
    cc.compile()

from my_module import proc
def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    C = np.empty(N+1, dtype=np.int32)
    C[0] = 0
    C[1:] = np.array(input().split(), dtype=np.int32)
    LR = np.array(sys.stdin.buffer.read().split(), dtype=np.uint32)
    L = LR[::2]
    R = LR[1::2]
    B = L>>9<<20|R
    Order = np.argsort(B)
    Ans = proc(C, L, R, Order, N, Q)
    print("\n".join(map(str, Ans.tolist())))

main()


### FIXED CODE ###

import sys
import numpy as np
def proc(C, L, R, Order, N, Q):
    pl = pr = 0
    ans = 0
    A = np.zeros(N+1, dtype=np.int32)
    Ans = np.zeros(Q, dtype=np.int32)
    for idx_LR in Order:
        l = L[idx_LR]
        r = R[idx_LR]
        while pr < r:
            pr += 1
            c = C[pr]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pl > l:
            pl -= 1
            c = C[pl]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pr > r:
            c = C[pr]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pr -= 1
        while pl < l:
            c = C[pl]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pl += 1
        Ans[idx_LR] = ans
    return Ans

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
    build = cc_export(proc, "i4[:](i4[:],u4[:],u4[:],i8[:],i4,i4)")
    cc.compile()

from my_module import proc
def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    C = np.empty(N+1, dtype=np.int32)
    C[0] = 0
    C[1:] = np.array(input().split(), dtype=np.int32)
    LR = np.array(sys.stdin.buffer.read().split(), dtype=np.uint32)
    L = LR[::2]
    R = LR[1::2]
    B = L>>9<<20|R
    Idx = (L>>9&1).astype(np.bool)
    B[Idx] = L[Idx]>>9<<20|(1<<20)-R[Idx]
    Order = np.argsort(B)
    Ans = proc(C, L, R, Order, N, Q)
    print("\n".join(map(str, Ans.tolist())))

main()