# Original solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, Q, C, LR):
    st = SegmentTree(f=lambda x, y: x | y, initial_values=[1 << (c - 1) for c in C])
    for l, r in LR:
        print((popcount(st.query(l - 1, r))))

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i << 1], d[i << 1 | 1])

    def get_val(self, index):
        return self.__d[index + self.__n]

    def set_val(self, index, new_value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == new_value: return
        d[i] = new_value
        while i:
            i = i >> 1
            d[i] = f(d[i << 1], d[i << 1 | 1])

    def modify(self, index, value):
        self.set_val(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l + 1
            if r & 1: ans, r = f(d[r - 1], ans), r - 1
            l, r = l >> 1, r >> 1
        return ans

if __name__ == '__main__':
    input = sys.stdin.readline
    N, Q = list(map(int, input().split()))
    *C, = list(map(int, input().split()))
    LR = [tuple(map(int, input().split())) for _ in range(Q)]
    main(N, Q, C, LR)


# Optimized solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, Q, C, LR):
    ans = [0] * Q
    LRi = [(l, r, i) for i, (l, r) in enumerate(LR)]
    LRi.sort(key=lambda x: x[1])
    bit = BinaryIndexedTree(N)
    MR = [-1] * (N + 1)
    p = 0
    for l, r, i in LRi:
        l, r = l - 1, r - 1
        while p <= r:
            c = C[p]
            mr = MR[c]
            if mr >= 0:
                bit.add(mr, -1)
            MR[c] = p
            bit.add(p, 1)
            p += 1
        ans[i] = bit.query(r) - bit.query(l - 1)
    for a in ans:
        print(a)

class BinaryIndexedTree:
    def __init__(self, n=None, f=lambda x, y: x + y, identity=0, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__id, = f, identity
        self.__n = len(initial_values) if initial_values else n
        self.__d = [identity] * (self.__n + 1)
        if initial_values:
            for i, v in enumerate(initial_values): self.add(i, v)

    def add(self, i, v):
        n, f, d = self.__n, self.__f, self.__d
        i += 1
        while i <= n:
            d[i] = f(d[i], v)
            i += -i & i

    def query(self, r):
        res, f, d = self.__id, self.__f, self.__d
        r += 1
        while r:
            res = f(res, d[r])
            r -= -r & r
        return res

if __name__ == '__main__':
    input = sys.stdin.readline
    N, Q = list(map(int, input().split()))
    *C, = list(map(int, input().split()))
    LR = [tuple(map(int, input().split())) for _ in range(Q)]
    main(N, Q, C, LR)