# Original solution
import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = list(map(int, input().split()))
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = list(map(int, input().split()))
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*q
    index = 0
    for i in range(n):
        bit.add(i+1, 1)
        if key[i] != -1:
            bit.add(key[i]+1, -1)
        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i:
                ans[query[index][2]] = bit.get_sum(l, r+1)
                index += 1
            else:
                break
        if index == q:
            break
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()



# Optimized solution
import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = list(map(int, input().split()))
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = list(map(int, input().split()))
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*q
    index = 0
    count = 0
    for i in range(n):
        if key[i] != -1:
            count += 1
            bit.add(key[i]+1, 1)
        while True:
            if index == q:
                break
            r, l, c = query[index]
            if r == i:
                ans[c] = r-l+1-count+bit.summarize(l)
                index += 1
            else:
                break
        if index == q:
            break
    
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()