### 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]]


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])
# print(lr)
now=0
# last[c[now-1]]=now
# # bi.add(now,1)
# print(last)
# print(bi.el)

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])

### 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()