### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    n,q=map(int,input().split())
    c=list(map(int,input().split()))
    lr=[list(map(int,input().split())) for i in range(q)]

    class SegTree:
        # init_valはseg木にしたいlist、ide_eleは単位元
        # """
        # 単位元の説明
        # 最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
        # 　　和のセグ木 → 0　(上の単位元の説明を参照)
        # 　　積のセグ木 → 1　(上の単位元の説明を参照)
        # 　　gcdのセグ木 → 0　(gcdを更新しない値は0)
        # """
        # funcは行いたい操作を代入
        # 区間の最小値を求めたいならmin
        # 区間の最大値を求めたいならmax
        # """
        def __init__(self, init_val, ide_ele):
            self.ide_ele=ide_ele
            self.num=2**(len(init_val)-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num
            # self.func=func

            #set_val
            for i in range(len(init_val)):
                self.seg[i+self.num-1]=init_val[i]
            #built
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])

        # 書け
        def segfunc(self, x, y):
            return x | y
        
        def update(self, k, x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])

        def query(self, p, q):
            if q<=p:
                return self.ide_ele
            p += self.num-1
            q += self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res,self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res,self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res,self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
            return res
    cc=[]
    for i in range(n):
        cc.append(set([c[i]]))
    # print(cc) 
    seg=SegTree(cc,set())
    # print(seg.seg)
    for i in range(q):
        l,r=lr[i]
        print(len(seg.query(l-1,r)))

main()

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    n,q=map(int,input().split())
    c=list(map(int,input().split()))
    lr=[list(map(int,input().split())) for i in range(q)]

    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0]*(n+1)
            self.el = [0]*(n+1)
        # [1,i]の足し算
        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s
        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i
        # [i,j]の足し算
        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i-1)

    for i in range(q):
        lr[i].append(i)
    last=[-1]*(n+1)
    bi=BIT(n)
    lr.sort(lambda x: x[1])
    now=0

    anslst=[-1]*q
    for i in range(q):
        l,r,j=lr[i]
        while now!=r:
            now+=1
            if last[c[now-1]]!=-1:
                bi.add(last[c[now-1]],-1)
            last[c[now-1]]=now
            bi.add(last[c[now-1]],1)
        # print(last)
        # print(bi.el)
        # print(bi.get(l,r))
        anslst[j]=bi.get(l,r)

    for i in range(q):
        print(anslst[i])

main()