from operator import add, mul, sub, or_





class SegmentTree:

    '''

    セグメント木(遅延ではない)

    1-indexd セグメント木

    values : 値の配列

    op : 区間に対する関数

    ie : 初期値

    '''



    def __init__(self, values):

        self.values = values

        vlen = len(values)

        self.size = 2 ** (vlen-1).bit_length()

        self.tree = [0]*self.size + self.values + [0]*(self.size-vlen)



        for i in range(self.size-1, 0, -1):

            self.tree[i] = self.tree[i*2] + self.tree[i*2+1]



    def update(self, i, v):

        i += self.size

        self.tree[i] = v

        while i > 0:

            i //= 2

            self.tree[i] = self.tree[i*2] + self.tree[i*2+1]



    def query(self, l, r):

        l += self.size

        r += self.size

        ret = 0

        while l < r:

            if l & 1:

                ret += self.tree[l]

                l += 1

            if r & 1:

                r -= 1

                ret += self.tree[r]

            l //= 2

            r //= 2

        return ret





N, Q = list(map(int, input().split()))

*c, = list(map(int, input().split()))



q = [[] for _ in range(N+1)]

for i in range(Q):

    x, y = list(map(int, input().split()))

    q[y-1].append([i, x-1])



st = SegmentTree([0]*(N+1))

finds = [-1]*(N+1)

ans = [0]*Q

for i in range(N):

    if finds[c[i]] != -1:

        st.update(finds[c[i]], 0)



    finds[c[i]] = i

    st.update(finds[c[i]], 1)



    for j, x in q[i]:

        ans[j] = st.query(x, i+1)



for a in ans:

    print(a)

class BIT:

    def __init__(self, n):

        self.n = n

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



    def update(self, i, v):

        while i <= self.n:

            self.tree[i] += v

            i += i & (-i)



    def query(self, i):

        v = 0

        while i:

            v += self.tree[i]

            i -= i & (-i)

        return v





N, Q = list(map(int, input().split()))

*c, = list(map(int, input().split()))



q = [[] for _ in range(N+1)]

for i in range(Q):

    x, y = list(map(int, input().split()))

    q[y-1].append([i, x-1])



bit = BIT(N)

finds = [-1]*(N+1)

ans = [0]*Q

for i in range(N):

    if finds[c[i]] != -1:

        bit.update(finds[c[i]]+1, -1)



    finds[c[i]] = i

    bit.update(finds[c[i]]+1, 1)



    for j, x in q[i]:

        ans[j] = bit.query(i+1) - bit.query(x)



for a in ans:

    print(a)

from operator import add, mul, sub, or_


class SegmentTree:
    """
    セグメント木(遅延ではない)
    1-indexd セグメント木
    values : 値の配列
    op : 区間に対する関数
    ie : 初期値
    """

    def __init__(self, values):
        self.values = values
        vlen = len(values)
        self.size = 2 ** (vlen - 1).bit_length()
        self.tree = [0] * self.size + self.values + [0] * (self.size - vlen)
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]

    def update(self, i, v):
        i += self.size
        self.tree[i] = v
        while i > 0:
            i //= 2
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]

    def query(self, l, r):
        l += self.size
        r += self.size
        ret = 0
        while l < r:
            if l & 1:
                ret += self.tree[l]
                l += 1
            if r & 1:
                r -= 1
                ret += self.tree[r]
            l //= 2
            r //= 2
        return ret


N, Q = list(map(int, input().split()))
(*c,) = list(map(int, input().split()))
q = [[] for _ in range(N + 1)]
for i in range(Q):
    x, y = list(map(int, input().split()))
    q[y - 1].append([i, x - 1])
st = SegmentTree([0] * (N + 1))
finds = [-1] * (N + 1)
ans = [0] * Q
for i in range(N):
    if finds[c[i]] != -1:
        st.update(finds[c[i]], 0)
    finds[c[i]] = i
    st.update(finds[c[i]], 1)
    for j, x in q[i]:
        ans[j] = st.query(x, i + 1)
for a in ans:
    print(a)

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

    def update(self, i, v):
        while i <= self.n:
            self.tree[i] += v
            i += i & (-i)

    def query(self, i):
        v = 0
        while i:
            v += self.tree[i]
            i -= i & (-i)
        return v


N, Q = list(map(int, input().split()))
(*c,) = list(map(int, input().split()))
q = [[] for _ in range(N + 1)]
for i in range(Q):
    x, y = list(map(int, input().split()))
    q[y - 1].append([i, x - 1])
bit = BIT(N)
finds = [-1] * (N + 1)
ans = [0] * Q
for i in range(N):
    if finds[c[i]] != -1:
        bit.update(finds[c[i]] + 1, -1)
    finds[c[i]] = i
    bit.update(finds[c[i]] + 1, 1)
    for j, x in q[i]:
        ans[j] = bit.query(i + 1) - bit.query(x)
for a in ans:
    print(a)

-from operator import add, mul, sub, or_ - - -class SegmentTree: -    """ -    セグメント木(遅延ではない) -    1-indexd セグメント木 -    values : 値の配列 -    op : 区間に対する関数 -    ie : 初期値 -    """ - -    def __init__(self, values): -        self.values = values -        vlen = len(values) -        self.size = 2 ** (vlen - 1).bit_length() -        self.tree = [0] * self.size + self.values + [0] * (self.size - vlen) -        for i in range(self.size - 1, 0, -1): -            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1] +class BIT: +    def __init__(self, n): +        self.n = n +        self.tree = [0] * (n + 1) -        i += self.size -        self.tree[i] = v -        while i > 0: -            i //= 2 -            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1] +        while i <= self.n: +            self.tree[i] += v +            i += i & (-i) -    def query(self, l, r): -        l += self.size -        r += self.size -        ret = 0 -        while l < r: -            if l & 1: -                ret += self.tree[l] -                l += 1 -            if r & 1: -                r -= 1 -                ret += self.tree[r] -            l //= 2 -            r //= 2 -        return ret +    def query(self, i): +        v = 0 +        while i: +            v += self.tree[i] +            i -= i & (-i) +        return v -st = SegmentTree([0] * (N + 1)) +bit = BIT(N) -        st.update(finds[c[i]], 0) +        bit.update(finds[c[i]] + 1, -1) -    st.update(finds[c[i]], 1) +    bit.update(finds[c[i]] + 1, 1) -        ans[j] = st.query(x, i + 1) +        ans[j] = bit.query(i + 1) - bit.query(x)