# Original solution
#!/usr/bin/env python3
class BinaryIndexedTree:
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size
 
    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return
 
    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res
 
    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
lr = [list(map(int, input().split())) + [i] for i in range(q)]
lr.sort(key=lambda x:x[1])
BIT = BinaryIndexedTree(n+1)
LastAppeared = [-1] * (n+1)
ans = [0] * q
R = 0
for l, r, i in lr:
    while R < r:
        if LastAppeared[c[R]] != -1:
            BIT.add(LastAppeared[c[R]], -1)
        LastAppeared[c[R]] = R+1
        BIT.add(R+1, 1)
        R += 1

    ans[i] = BIT.sum(r) - BIT.sum(l-1)
for i in ans:
    print(i)

# Optimized solution
#!/usr/bin/env python3
import sys
class BinaryIndexedTree:
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size
 
    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return
 
    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res
 
    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

n, q = list(map(int, sys.stdin.readline().split()))
c = list(map(int, sys.stdin.readline().split()))
lr = [list(map(int, sys.stdin.readline().split())) + [i] for i in range(q)]
lr.sort(key=lambda x:x[1])
BIT = BinaryIndexedTree(n+1)
LastAppeared = [-1] * (n+1)
ans = [0] * q
R = 0
for l, r, i in lr:
    while R < r:
        if LastAppeared[c[R]] != -1:
            BIT.add(LastAppeared[c[R]], -1)
        LastAppeared[c[R]] = R+1
        BIT.add(R+1, 1)
        R += 1
    ans[i] = BIT.sum(r) - BIT.sum(l-1)

for i in ans:
    print(i)