### BUGGY CODE ###

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 = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [list(map(int, input().split())) for _ in range(q)]
    for i in range(q):
        qry[i].append(i)
    qry.sort(key=lambda x: x[1])
    col_var = [0]*n
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, col_var)
    for i in range(q):
        l, r = qry[i][:2]
        l -= 1
        if last_update_idx < r:
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    col_var[dic[color[j]]] = 0
                    seg.update(dic[color[j]], 0)
                col_var[j] = 1
                seg.update(j, 1)
                dic[color[j]] = j
            last_update_idx = r
        qry[i].append(seg.query(l, r))
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = 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 not color[j] in st and color[j] in dic:
                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)