### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

class Segment_tree():
    def __init__(self, n, arrange):
        self.inf = pow(2, 32)
        self.n = n
        self.arrange = arrange
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [set()]*(self.N) + self.arrange + [set()]*(self.size-self.N-self.n)
        #この次の処理は、求められる動作に応じて変化させる。ここでは区間最小値問題のコードを書く。
        for i in range(self.N-1, -1, -1):
            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 set()
        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()]
    key = [None]*n
    
    judge = dict()
    for i in range(n-1, -1, -1):
        if c[i] in judge:
            key[i] = {judge[c[i]]}
        else:
            key[i] = set()
        judge[c[i]] = i
    """
    key2 = [None]*n
    
    judge2 = dict()
    for i in range(n):
        if c[i] in judge2:
            key2[i] = {judge2[c[i]]}
        else:
            key2[i] = set()
        judge2[c[i]] = i
     """   
    segment = Segment_tree(n, key)
    for i in range(q):
        l, r = map(int, input().split())
        judgement = sorted(list(segment.count(l-1, r-1)))
        print(r-l+1-bisect.bisect_left(judgement, r))
    
    
    
    
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()