### BUGGY CODE ###

import sys
input = sys.stdin.readline


class Segment_tree():
    def __init__(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [0]*(self.size)
        for i in range(self.N-1, -1, -1):
            self.segment[i] = self.segment[2*i+1]+self.segment[2*i+2]
        
    def undate(self, i, x):
        i += (self.N)
        self.segment[i] = x
        while i > 0:
            i = (i-1)//2
            self.segment[i] = self.segment[2*i+1]+self.segment[2*i+2]
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return find_l+find_r
    
    def count(self, l, r):
        return self.find(l, r, 0, 0, self.size-self.N)


def main():
    n, q = 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 = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    segment = Segment_tree(n)
    ans = [0]*q
    index = 0
    for i in range(n):
        segment.undate(i, 1)
        if key[i] != -1:
            segment.undate(key[i], 0)
        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i:
                ans[query[index][2]] = segment.count(l, r+1)
                index += 1
            else:
                break
        if index == q:
            break
    
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()



### FIXED CODE ###

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def sum(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 subtract(self, i, x):
        self.add(i, -x)
    
    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.sum(j) - self.sum(i)
    
    def lower_bound(self, x):#和がx以上になる最小のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):#和がx以下になる最大のインデックス
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()