# Original solution
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = list(map(int, input().split()))
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = list(map(int, input().split()))
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j, col in enumerate(color[last_update_idx: r]):
                if not col in st and col in dic:
                    seg.update(dic[col], 0)
                dic[col] = j+last_update_idx
                st.add(col)
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


# Optimized solution
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = list(map(int, input().split()))
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = list(map(int, input().split()))
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if color[j] in dic and not color[j] in st:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()