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 = list(map(int, input().split()))

color = list(map(int, input().split()))

qry = [None]*q

ans = [0]*q

p = 0

for _ in ans:

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

from sys import stdin

input = stdin.readline

class Bit:

    def __init__(self, n):

        self.size = n

        self.tree = [0] * (n + 1)

 

    def sum(self, i):

        s = 0

        while i > 0:

            s += self.tree[i]

            i -= i & -i

        return s

 

    def add(self, i, x):

        while i <= self.size:

            self.tree[i] += x

            i += i & -i



n, q = list(map(int, input().split()))

tmp = list(map(int, input().split()))

color = [-1]

for v in tmp:

    color.append(v)

qry = [None]*q

ans = [0]*q

p = 0

for _ in ans:

    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 = 1

bit = Bit(n)

for l, r, i in qry:

    if last_update_idx < r+1:

        st = set()

        for j in range(last_update_idx, r+1):

            if not color[j] in st and color[j] in dic:

                bit.add(dic[color[j]], -1)

            dic[color[j]] = j

            st.add(color[j])

        for v in st:

            bit.add(dic[v], 1)

        last_update_idx = r+1

    ans[i] = bit.sum(r) - bit.sum(l)

for v in ans:

    print(v)

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

from sys import stdin

input = stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, q = list(map(int, input().split()))
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
qry = [None] * q
ans = [0] * q
p = 0
for _ in ans:
    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 = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r + 1:
        st = set()
        for j in range(last_update_idx, r + 1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r + 1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)

-class SegTree: -    def segfunc(self, x, y): -        return x + y +class Bit: +    def __init__(self, n): +        self.size = n +        self.tree = [0] * (n + 1) -    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 sum(self, i): +        s = 0 +        while i > 0: +            s += self.tree[i] +            i -= i & -i +        return s -    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 add(self, i, x): +        while i <= self.size: +            self.tree[i] += x +            i += i & -i -color = list(map(int, input().split())) +tmp = list(map(int, input().split())) +color = [-1] +for v in tmp: +    color.append(v) -last_update_idx = 0 -seg = SegTree(0, n, [0] * n) +last_update_idx = 1 +bit = Bit(n) -    if last_update_idx < r: +    if last_update_idx < r + 1: -        for j in range(last_update_idx, r): +        for j in range(last_update_idx, r + 1): -                seg.update(dic[color[j]], 0) +                bit.add(dic[color[j]], -1) -            seg.update(dic[v], 1) -        last_update_idx = r -    ans[i] = seg.query(l, r) +            bit.add(dic[v], 1) +        last_update_idx = r + 1 +    ans[i] = bit.sum(r) - bit.sum(l)