### BUGGY CODE ###

import io
import os


# Mo's algorithm for counting distinct in a range
# O(N*sqrt(N)), TLEs on 5*10**5
# From https://www.geeksforgeeks.org/mos-algorithm-query-square-root-decomposition-set-1-introduction/
def solve(N, Q, C, L, R):
    BLOCK = int(Q ** 0.5)
    order = range(Q)
    order = sorted(order, key=lambda i: R[i])
    order = sorted(order, key=lambda i: L[i] // 2048)

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

    ans = [0 for i in range(Q)]
    for i in order:
        l, r = L[i], R[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

        # assert len([i for i, x in enumerate(countUniq) if x > 0]) == numUniq
        # 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 True:
    import random

    random.seed(0)
    N = 5 * 10 ** 5
    Q = 5 * 10 ** 5
    C = [random.randint(1, N) for i in range(N)]
    L = []
    R = []
    for i in range(Q):
        l = random.randint(0, N - 1)
        r = random.randint(0, N - 1)
        if l > r:
            l, r = r, l
        L.append(l)
        R.append(r)
    solve(N, Q, C, L, R)
    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()]
    L = []
    R = []
    for i in range(Q):
        # 0-indexed, inclusive inclusive
        l, r = [int(x) - 1 for x in input().split()]
        L.append(l)
        R.append(r)
    print(solve(N, Q, C, L, R))


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