Buggy python submission (verdict: Time Limit Exceeded):
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):
    # Mo's order, first by block, then zigzag depending of parity of block
    MAX_R = 1 << 20

    def moOrder(i):
        l, r = L[i], R[i]
        b = l >> 10  # Block size of 1024
        r = (MAX_R - r) if b % 2 else r  # Decreasing r if block odd
        # assert 0 <= y < MAX_R
        return b * MAX_R + r

    order = sorted(range(Q), key=moOrder)

    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 currR <= r:
            x = C[currR]
            numUniq += int(countUniq[x] == 0)
            countUniq[x] += 1
            currR += 1
        while currR > r + 1:
            x = C[currR - 1]
            countUniq[x] -= 1
            numUniq -= int(countUniq[x] == 0)
            currR -= 1
        while currL < l:
            x = C[currL]
            countUniq[x] -= 1
            numUniq -= int(countUniq[x] == 0)
            currL += 1
        while currL > l:
            x = C[currL - 1]
            numUniq += int(countUniq[x] == 0)
            countUniq[x] += 1
            currL -= 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 False:
    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 submission:
# 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))

Buggy python submission (verdict: Time Limit Exceeded):
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 submission:
# 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))

Buggy python submission (verdict: Time Limit Exceeded):
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 submission:
# 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))

Buggy python submission (verdict: Time Limit Exceeded):
import io
import os


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

    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
    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(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
    solve(N, Q, C, LR)


Fixed submission:
# 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))

Buggy python submission (verdict: Time Limit Exceeded):
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(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)


Fixed submission:
# 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))

Buggy python submission (verdict: Time Limit Exceeded):
# 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
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 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)


Fixed submission:
# 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))