### BUGGY CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s


n, q = map(int, input().split())
c = list(map(int, input().split()))
queries = []
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    queries.append((i, l, r))
queries.sort(key=itemgetter(2))

ans = [0] * q
# last_visit[i] = 色iの最後のindex
last_visit = [-1] * (n + 1)
query_counter = 0
bit = BIT1(n)
for i in range(n):
    if last_visit[c[i]] != -1:
        bit.add(last_visit[c[i]] + 1, -1)

    last_visit[c[i]] = i
    bit.add(i + 1, +1)

    while query_counter < q and queries[query_counter][2] == i:
        idx, l, r = queries[query_counter]
        ans[idx] = bit.sum(r + 1) - bit.sum(l)
        query_counter += 1

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


### FIXED CODE ###

from operator import attrgetter
# Python3 code to find number of
# distinct numbers in a subarray
MAX = 6 * 10**5


# structure to store queries
class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx


# updating the bit array
def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx


# querying the bit array
def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):

    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of
    # any number as numbers of a[i]
    # are less than or equal to 10^6
    last_visit = [-1] * MAX

    # answer for each query
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the
        # idx equal to last_visit[arr[i]]
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

        # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer
        # for that query in ans[]
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                        query(queries[query_counter].r + 1, bit, n) - \
                        query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query
    for i in range(q):
        print(ans[i])


def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    queries = []
    for i in range(q):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        queries.append(Query(l, r, i))
    queries.sort(key=attrgetter('r'))

    answeringQueries(c, n, queries, q)


if __name__ == "__main__":
    main()