# Original solution
# From: https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SegmentTree.py
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size : _size + self._len] = data
        for i in reversed(list(range(_size))):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


import io
import os
from collections import defaultdict
from bisect import bisect_left, bisect_right


def solve(N, Q, C, LR):
    valToIndices = defaultdict(list)
    for i, c in enumerate(C):
        valToIndices[c].append(i)
    THRESHOLD = 500
    autoIncrement = defaultdict(lambda: len(autoIncrement))
    data = [0] * N
    for i, c in enumerate(C):
        if len(valToIndices[c]) < THRESHOLD:
            data[i] = 1 << autoIncrement[c]
    for k in list(valToIndices.keys()):
        if len(valToIndices[k]) < THRESHOLD:
            del valToIndices[k]
    segTree = SegmentTree(data, 0, lambda x, y: x | y)

    for l, r in LR:
        r += 1
        mask = segTree.query(l, r)
        lowFreqCount = 0
        while mask:
            lowFreqCount += mask & 1
            mask >>= 1
        highFreqCount = 0
        for x, indices in list(valToIndices.items()):
            if bisect_right(indices, r - 1) - bisect_left(indices, l):
                highFreqCount += 1
        print((lowFreqCount + highFreqCount))


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    N, Q = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    LR = [[int(x) - 1 for x in input().split()] for i in range(Q)]  # 0-indexed
    solve(N, Q, C, LR)


# Optimized solution
import io
import os
from collections import Counter

from bisect import bisect_left, bisect_right


# From https://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/
def solve(C, LR):
    order = sorted(list(range(len(LR))), key=lambda i: LR[i][1])

    currL, currR = 0, 0
    currUniq = Counter()

    ans = [0] * len(LR)
    for i in order:
        L, R = LR[i]

        while currL < L:
            x = C[currL]
            currUniq[x] -= 1
            if currUniq[x] == 0:
                del currUniq[x]
            currL += 1

        while currL > L:
            x = C[currL - 1]
            currUniq[x] += 1
            if currUniq[x] == 0:
                del currUniq[x]
            currL -= 1
        while currR <= R:
            x = C[currR]
            currUniq[x] += 1
            if currUniq[x] == 0:
                del currUniq[x]
            currR += 1

        while currR > R + 1:
            x = C[currR - 1]
            currUniq[x] -= 1
            if currUniq[x] == 0:
                del currUniq[x]
            currR -= 1

        # print(C[L : R + 1], "is", currUniq)
        ans[i] = len(currUniq)
    print(("\n".join(map(str, ans))))


if False:
    import random

    random.seed(0)
    N = 5 * 10 ** 5
    Q = 5 * 10 ** 5
    C = [random.randint(1, N) for i in range(N)]
    LR = []
    for i in range(Q):
        l = random.randint(1, N)
        r = random.randint(1, N)
        if l > r:
            l, r = r, l
        LR.append((l, r))
    solve(C, LR)
    exit()


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    N, Q = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    LR = [[int(x) - 1 for x in input().split()] for i in range(Q)]  # 0-indexed
    solve(C, LR)