import sys

read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines

 

 



class SegmentTree:

    def __init__(self, a):

        self.padding = 0

        self.n = len(a)

        self.N = 2 ** (self.n-1).bit_length()

        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)

        for i in range(2*self.N-2, 0, -2):

            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]

    

    def __len__(self):

        return self.n

    

    def update(self, i, x):

        idx = self.N - 1 + i

        self.seg_data[idx] = x

        while idx:

            idx = (idx-1) // 2

            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]

    

    def query(self, i, j):

        # [i, j)

        if i == j:

            return self.seg_data[self.N - 1 + i]

        else:

            idx1 = self.N - 1 + i

            idx2 = self.N - 2 + j # 閉区間にする

            result = self.padding

            while idx1 < idx2 + 1:

                if idx1&1 == 0: # idx1が偶数

                    result = result + self.seg_data[idx1]

                if idx2&1 == 1: # idx2が奇数

                    result = result + self.seg_data[idx2]

                    idx2 -= 1

                idx1 //= 2

                idx2 = (idx2 - 1)//2

            return result

    

    @property

    def data(self):

        return self.seg_data[self.N-1:self.N-1+self.n]





N, Q = map(int, readline().split())

C = list(map(int, readline().split()))

data = list(map(int,read().split()))

lr = [[i, data[2*i], data[2*i+1]] for i in range(0, Q)]

lr.sort(key=lambda x:x[2])



ans = [0] * Q

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

st = SegmentTree([0]*N)



now = 0

for i, l, r in lr:

    l -= 1

    while now < r:

        c = C[now]

        pre_idx, last_appeared[c] = last_appeared[c], now

        if pre_idx >= 0:

            st.update(pre_idx, 0)

        st.update(now, 1)

        now += 1

    ans[i] = st.query(l, r)





print(*ans, sep='\n')

class SegmentTree:

    def __init__(self, a):

        self.padding = 0

        self.n = len(a)

        self.N = 2 ** (self.n-1).bit_length()

        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)

        for i in range(2*self.N-2, 0, -2):

            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]

    

    def __len__(self):

        return self.n

    

    def update(self, i, x):

        idx = self.N - 1 + i

        self.seg_data[idx] = x

        while idx:

            idx = (idx-1) // 2

            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]

    

    def query(self, i, j):

        # [i, j)

        if i == j:

            return self.seg_data[self.N - 1 + i]

        else:

            idx1 = self.N - 1 + i

            idx2 = self.N - 2 + j # 閉区間にする

            result = self.padding

            while idx1 < idx2 + 1:

                if idx1&1 == 0: # idx1が偶数

                    result = result + self.seg_data[idx1]

                if idx2&1 == 1: # idx2が奇数

                    result = result + self.seg_data[idx2]

                    idx2 -= 1

                idx1 //= 2

                idx2 = (idx2 - 1)//2

            return result

    

    @property

    def data(self):

        return self.seg_data[self.N-1:self.N-1+self.n]





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

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

ans = [0] * Q

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

st = SegmentTree([0]*N)

li = [[] for i in range(N+1)]

for i in range(Q):

    l, r = map(int, input().split())

    li[r].append((i, l-1))



now = 0

for r in range(1, N+1):

    for i, l in li[r]:

        while now < r:

            c = C[now]

            pre_idx, last_appeared[c] = last_appeared[c], now

            if pre_idx >= 0:

                st.update(pre_idx, 0)

            st.update(now, 1)

            now += 1

        ans[i] = st.query(l, r)





print(*ans, sep='\n')

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n - 1).bit_length()
        self.seg_data = (
            [self.padding] * (self.N - 1) + a + [self.padding] * (self.N - self.n)
        )
        for i in range(2 * self.N - 2, 0, -2):
            self.seg_data[(i - 1) // 2] = self.seg_data[i] + self.seg_data[i - 1]

    def __len__(self):
        return self.n

    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx - 1) // 2
            self.seg_data[idx] = self.seg_data[2 * idx + 1] + self.seg_data[2 * idx + 2]

    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j  # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1 & 1 == 0:  # idx1が偶数
                    result = result + self.seg_data[idx1]
                if idx2 & 1 == 1:  # idx2が奇数
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1) // 2
            return result

    @property
    def data(self):
        return self.seg_data[self.N - 1 : self.N - 1 + self.n]


N, Q = map(int, readline().split())
C = list(map(int, readline().split()))
data = list(map(int, read().split()))
lr = [[i, data[2 * i], data[2 * i + 1]] for i in range(0, Q)]
lr.sort(key=lambda x: x[2])
ans = [0] * Q
last_appeared = [-1] * (N + 1)
st = SegmentTree([0] * N)
now = 0
for i, l, r in lr:
    l -= 1
    while now < r:
        c = C[now]
        pre_idx, last_appeared[c] = last_appeared[c], now
        if pre_idx >= 0:
            st.update(pre_idx, 0)
        st.update(now, 1)
        now += 1
    ans[i] = st.query(l, r)
print(*ans, sep="\n")

class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n - 1).bit_length()
        self.seg_data = (
            [self.padding] * (self.N - 1) + a + [self.padding] * (self.N - self.n)
        )
        for i in range(2 * self.N - 2, 0, -2):
            self.seg_data[(i - 1) // 2] = self.seg_data[i] + self.seg_data[i - 1]

    def __len__(self):
        return self.n

    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx - 1) // 2
            self.seg_data[idx] = self.seg_data[2 * idx + 1] + self.seg_data[2 * idx + 2]

    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j  # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1 & 1 == 0:  # idx1が偶数
                    result = result + self.seg_data[idx1]
                if idx2 & 1 == 1:  # idx2が奇数
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1) // 2
            return result

    @property
    def data(self):
        return self.seg_data[self.N - 1 : self.N - 1 + self.n]


N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0] * Q
last_appeared = [-1] * (N + 1)
st = SegmentTree([0] * N)
li = [[] for i in range(N + 1)]
for i in range(Q):
    l, r = map(int, input().split())
    li[r].append((i, l - 1))
now = 0
for r in range(1, N + 1):
    for i, l in li[r]:
        while now < r:
            c = C[now]
            pre_idx, last_appeared[c] = last_appeared[c], now
            if pre_idx >= 0:
                st.update(pre_idx, 0)
            st.update(now, 1)
            now += 1
        ans[i] = st.query(l, r)
print(*ans, sep="\n")

-import sys - -read = sys.stdin.buffer.read -readline = sys.stdin.buffer.readline -readlines = sys.stdin.buffer.readlines - - -N, Q = map(int, readline().split()) -C = list(map(int, readline().split())) -data = list(map(int, read().split())) -lr = [[i, data[2 * i], data[2 * i + 1]] for i in range(0, Q)] -lr.sort(key=lambda x: x[2]) +N, Q = map(int, input().split()) +C = list(map(int, input().split())) +li = [[] for i in range(N + 1)] +for i in range(Q): +    l, r = map(int, input().split()) +    li[r].append((i, l - 1)) -for i, l, r in lr: -    l -= 1 -    while now < r: -        c = C[now] -        pre_idx, last_appeared[c] = last_appeared[c], now -        if pre_idx >= 0: -            st.update(pre_idx, 0) -        st.update(now, 1) -        now += 1 -    ans[i] = st.query(l, r) +for r in range(1, N + 1): +    for i, l in li[r]: +        while now < r: +            c = C[now] +            pre_idx, last_appeared[c] = last_appeared[c], now +            if pre_idx >= 0: +                st.update(pre_idx, 0) +            st.update(now, 1) +            now += 1 +        ans[i] = st.query(l, r)