Buggy python submission (verdict: Time Limit Exceeded):
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        # self.el = [0]*(n+1)
    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
            #print(i)
    '''
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
    '''

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

query = []

for i in range(Q):
    l,r = map(int,input().split())
    query.append((i,l,r))

query.sort(key = lambda x:x[2])

###
#print(query)
###

ans = [0]*Q
place = [-1]*(N+1)###各色のいい玉がどこにあるか、なければ-1
next_query = 0

bit = BIT(N)

###
#print(bit)
###

for i in range(N):

    bit.add(i+1,1)

    if place[c[i]] != -1:
        bit.add(place[c[i]]+1,-1)

    place[c[i]] = i

    #print(i,bit.data,place)

    while next_query < len(query) and query[next_query][2] == i+1:
        ###
        #print(query[next_query])
        ###
        j,l,r = query[next_query]
        ans[j] = bit.sum(r)-bit.sum(l-1)###l,rは入力時のまま(1-indexed)であることに注意
        next_query += 1
        ###
        #print(i,ans)
        ###
        

    ###
    #print(i,ans)
    ###
    
for i in range(Q):
    print(ans[i])





Fixed submission:
from sys import stdin

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        # self.el = [0]*(n+1)
    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
            #print(i)
    '''
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
    '''

N,Q = map(int, stdin.readline().split())
c = list(map(int, stdin.readline().split()))

query = []

for i in range(Q):
    l,r = map(int, stdin.readline().split())
    query.append((i,l,r))

query.sort(key = lambda x:x[2])

###
#print(query)
###

ans = [0]*Q
place = [-1]*(N+1)###各色のいい玉がどこにあるか、なければ-1
next_query = 0

bit = BIT(N)

###
#print(bit)
###

for i in range(N):

    bit.add(i+1,1)

    if place[c[i]] != -1:
        bit.add(place[c[i]]+1,-1)

    place[c[i]] = i

    #print(i,bit.data,place)

    while next_query < len(query) and query[next_query][2] == i+1:
        ###
        #print(query[next_query])
        ###
        j,l,r = query[next_query]
        ans[j] = bit.sum(r)-bit.sum(l-1)###l,rは入力時のまま(1-indexed)であることに注意
        next_query += 1
        ###
        #print(i,ans)
        ###
        

    ###
    #print(i,ans)
    ###
    
'''
for i in range(Q):
    print(ans[i])
'''

print(*ans,sep='\n')

Buggy python submission (verdict: Time Limit Exceeded):
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        # self.el = [0]*(n+1)
    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
            #print(i)
    '''
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
    '''

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

query = []

for i in range(Q):
    l,r = map(int,input().split())
    query.append((i,l,r))

query.sort(key = lambda x:x[2])

###
#print(query)
###

ans = [0]*Q
place = [-1]*(N+1)###各色のいい玉がどこにあるか、なければ-1
next_query = 0

bit = BIT(N)

###
#print(bit)
###

for i in range(N):

    bit.add(i+1,1)

    if place[c[i]] != -1:
        bit.add(place[c[i]]+1,-1)

    place[c[i]] = i

    #print(i,bit.data,place)

    while next_query < len(query) and query[next_query][2] == i+1:
        ###
        #print(query[next_query])
        ###
        j,l,r = query[next_query]
        ans[j] = bit.sum(r)-bit.sum(l-1)###l,rは入力時のまま(1-indexed)であることに注意
        next_query += 1
        ###
        #print(i,ans)
        ###
        

    ###
    #print(i,ans)
    ###
    
for i in range(Q):
    print(ans[i])





Fixed submission:
from sys import stdin

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        # self.el = [0]*(n+1)
    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
            #print(i)
    '''
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
    '''

N,Q = map(int, stdin.readline().split())
c = list(map(int, stdin.readline().split()))

query = []

for i in range(Q):
    l,r = map(int, stdin.readline().split())
    query.append((i,l,r))

query.sort(key = lambda x:x[2])

###
#print(query)
###

ans = [0]*Q
place = [-1]*(N+1)###各色のいい玉がどこにあるか、なければ-1
next_query = 0

bit = BIT(N)

###
#print(bit)
###

for i in range(N):

    bit.add(i+1,1)

    if place[c[i]] != -1:
        bit.add(place[c[i]]+1,-1)

    place[c[i]] = i

    #print(i,bit.data,place)

    while next_query < len(query) and query[next_query][2] == i+1:
        ###
        #print(query[next_query])
        ###
        j,l,r = query[next_query]
        ans[j] = bit.sum(r)-bit.sum(l-1)###l,rは入力時のまま(1-indexed)であることに注意
        next_query += 1
        ###
        #print(i,ans)
        ###
        

    ###
    #print(i,ans)
    ###
    
'''
for i in range(Q):
    print(ans[i])
'''

print(*ans,sep='\n')