import sys



input = sys.stdin.readline



def query(i):

    '''

    a[0] + a[1] + … + a[i-1] を求める

    O(logN)

    '''

    res = 0

    while i > 0:

        res += BIT[i]

        i -= i & -i

    

    return res





def update(i, x):

    '''

    a[i-1]にxを加算

    O(logN)

    '''

    while i <= n:

        BIT[i] += x

        i += i & -i





n, q = list(map(int, input().split()))

c = list(map(int, input().split()))

query_ = [list(map(int, input().split())) + [i] for i in range(q)]



query_.sort(key=lambda x: x[1])



res = [0] * q

pos = [-1] * n

BIT = [0] * (n+1)

p = 0

for l, r, idx in query_:

    for i in range(p, r):

        if pos[c[i]-1] != -1:

            update(pos[c[i]-1]+1, -1)

        update(i+1, 1)

        pos[c[i]-1] = i

    

    res[idx] = query(r) - query(l-1)

    p = r



for v in res:

    print(v)
import sys



input = sys.stdin.buffer.readline



def query(i):

    '''

    a[0] + a[1] + … + a[i-1] を求める

    O(logN)

    '''

    res = 0

    while i > 0:

        res += BIT[i]

        i -= i & -i

    

    return res





def update(i, x):

    '''

    a[i-1]にxを加算

    O(logN)

    '''

    while i <= n:

        BIT[i] += x

        i += i & -i





n, q = list(map(int, input().split()))

c = list(map(int, input().split()))

query_ = [list(map(int, input().split())) + [i] for i in range(q)]



query_.sort(key=lambda x: x[1])



res = [0] * q

pos = [-1] * n

BIT = [0] * (n+1)

p = 0

for l, r, idx in query_:

    for i in range(p, r):

        if pos[c[i]-1] != -1:

            update(pos[c[i]-1]+1, -1)

        update(i+1, 1)

        pos[c[i]-1] = i

    

    res[idx] = query(r) - query(l-1)

    p = r



for v in res:

    print(v)
import sys

input = sys.stdin.readline


def query(i):
    """
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    """
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    return res


def update(i, x):
    """
    a[i-1]にxを加算
    O(logN)
    """
    while i <= n:
        BIT[i] += x
        i += i & -i


n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]
query_.sort(key=lambda x: x[1])
res = [0] * q
pos = [-1] * n
BIT = [0] * (n + 1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i] - 1] != -1:
            update(pos[c[i] - 1] + 1, -1)
        update(i + 1, 1)
        pos[c[i] - 1] = i
    res[idx] = query(r) - query(l - 1)
    p = r
for v in res:
    print(v)

import sys

input = sys.stdin.buffer.readline


def query(i):
    """
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    """
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    return res


def update(i, x):
    """
    a[i-1]にxを加算
    O(logN)
    """
    while i <= n:
        BIT[i] += x
        i += i & -i


n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]
query_.sort(key=lambda x: x[1])
res = [0] * q
pos = [-1] * n
BIT = [0] * (n + 1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i] - 1] != -1:
            update(pos[c[i] - 1] + 1, -1)
        update(i + 1, 1)
        pos[c[i] - 1] = i
    res[idx] = query(r) - query(l - 1)
    p = r
for v in res:
    print(v)

-input = sys.stdin.readline +input = sys.stdin.buffer.readline