# Original solution
from collections import Counter
from operator import add

class SegmentTree():

    def __init__(self, iterable, func, e):
        self.func = func
        self.e = e
        ls = list(iterable)
        self.n = 1 << len(ls).bit_length()
        ls.extend( [self.e] * (self.n - len(ls)) )
        self.data = [self.e] * self.n + ls
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index //= 2
        
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)


N, Q = list(map(int, input().split()))
cs = list(map(int, input().split()))
lrs = [tuple(map(int, input().split())) for _ in range(Q)]

to_consider = []
for c, n in list(Counter(cs).items()):
    if n >= 2:
        to_consider.append(c)

sets = SegmentTree([Counter([e]) if e in to_consider else Counter() for e in cs], add, Counter())
for l, r in lrs:
    ans = r - l + 1
    for k, v in list(sets.folded(l-1, r).items()):
        ans -= (v - 1)
    print(ans)


# Optimized solution
from operator import add

class BIT():

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [self.e] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [self.e] + length_or_list
            for i in range(1, self.n):
                self.data[i + (i & -i)] = self.func(self.data[i + (i & -i)], self.data[i])        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.func(self.data[index], delta)
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res = self.func(res, self.data[end])
            end -= end & -end
        return res


N, Q = map(int, input().split())
cs = list(map(int, input().split()))
lrs = [tuple(map(int, input().split())) for _ in range(Q)]

#クエリを終了位置rでソート。
ilrs = [(i, l-1, r-1) for i, (l, r) in enumerate(lrs)]
ilrs.sort(key = lambda t: t[2])

#重複を区間としてし、終了位置でソートされた状態で列挙。
duplicates = []
indices = [-1 for _ in range(N+1)]
for i, c in enumerate(cs):
    if indices[c] != -1:
        duplicates.append((indices[c], i))
    indices[c] = i

#あとは平面走査と呼ばれる探査
ilrs.reverse()
duplicates.reverse()
starts = BIT(N, add, 0)
ans = [-1] * Q
for i in range(N):
    if duplicates and duplicates[-1][1] == i:
        dupstart, _ = duplicates.pop()
        starts.point_append(dupstart, 1)
    while ilrs[-1][2] == i:
        ans_i, l, r = ilrs.pop()
        ans[ans_i] = (r - l + 1) - (starts.prefix_folded(r + 1) - starts.prefix_folded(l))
        if not ilrs:
            break
    else:
        continue
    break

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