### BUGGY CODE ###

import io
import os


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

    currL, currR = 0, 0
    countUniq = [0 for i in range(N + 1)]
    numUniq = 0

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

        while currL < L:
            x = C[currL]
            countUniq[x] -= 1
            if countUniq[x] == 0:
                numUniq -= 1
            currL += 1

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

        while currR > R + 1:
            x = C[currR - 1]
            countUniq[x] -= 1
            if countUniq[x] == 0:
                numUniq -= 1
            currR -= 1

        # print(C[L : R + 1], "is", [i for i, x in enumerate(countUniq) if x > 0], numUniq)
        ans[i] = numUniq
    return "\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(N, Q, 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
    print(solve(N, Q, C, LR))


### FIXED CODE ###

# 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(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


def solve(N, Q, C, LR):
    # Bucket sort queries by right endpoint
    LByR = defaultdict(list)
    for i, (l, r) in enumerate(LR):
        LByR[r].append((i, l))

    # Segment tree stores a 1 at position i if the ith element is the rightmost of its dupes
    segTree = SegmentTree([0] * (N + 1), 0, lambda x, y: x + y)
    lastSeen = {}
    ans = [0] * Q
    for r, x in enumerate(C):
        if x in lastSeen:
            # Clear the previous rightmost bit
            segTree[lastSeen[x]] -= 1
        # Add a new rightmost bit
        segTree[r] += 1
        lastSeen[x] = r

        for queryIndex, l in LByR[r]:
            ans[queryIndex] = segTree.query(l, r + 1)

    return "\n".join(map(str, ans))


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()]
    # 0-indexed, inclusive inclusive
    LR = [[int(x) - 1 for x in input().split()] for i in range(Q)]
    print(solve(N, Q, C, LR))