Problem:
 Score : 600 points    Problem Statement We have N colored balls arranged in a row from left to right; the color of the i -th ball from the left is c_i .  You are given Q queries. The i -th query is as follows: how many different colors do the l_i -th through r_i -th balls from the left have?      Constraints  1\leq N,Q \leq 5 \times 10^5  1\leq c_i \leq N  1\leq l_i \leq r_i \leq N  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  Q  c_1  c_2  \cdots  c_N  l_1  r_1  l_2  r_2  :  l_Q  r_Q       Output Print Q lines. The i -th line should contain the response to the i -th query.        Sample Input 1 4 3
1 2 1 3
1 3
2 4
3 3      Sample Output 1 2
3
1   The 1 -st, 2 -nd, and 3 -rd balls from the left have the colors 1 , 2 , and 1 - two different colors.  The 2 -st, 3 -rd, and 4 -th balls from the left have the colors 2 , 1 , and 3 - three different colors.  The 3 -rd ball from the left has the color 1 - just one color.        Sample Input 2 10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8      Sample Output 2 1
2
2
1
2
2
6
3
3
3

Solution (Python):
class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.size = size+1
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < self.size:
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right



def solve(C, queries):
    N = len(C)
    Q = len(queries)
    bit = BinaryIndexedTree(N)

    last_ind = [None]*(N + 1)
    sorted_qi = sorted(range(Q), key=lambda i:queries[i][1])

    res = [None]*Q
    pr = 0
    temp = 0
    for qi in sorted_qi:
        l,r = queries[qi]
        for j,c in enumerate(C[pr:r],start=pr):
            if last_ind[c] is not None:
                bit._add(last_ind[c], -1)
            else:
                temp += 1
            last_ind[c] = j
            bit._add(j, 1)

        pr = r
        res[qi] = temp - bit._get_sum(l-1)

    return res














import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':
    N,Q = map(int,readline().split())
    C = list(map(int,readline().split()))

    m = map(int,read().split())
    queries = list(zip(m,m))

    print(*solve(C,queries), sep='\n')

Solution (Python):
class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.size = size+1
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < self.size:
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right



def solve(C, queries):
    N = len(C)
    Q = len(queries)
    bit = BinaryIndexedTree(N)

    last_ind = [None]*(N + 1)
    sorted_qi = sorted(range(Q), key=lambda i:queries[i][1])

    res = [None]*Q
    pr = 0
    temp = 0
    for qi in sorted_qi:
        l,r = queries[qi]
        for j,c in enumerate(C[pr:r],start=pr):
            c = C[j]
            if last_ind[c] is not None:
                bit._add(last_ind[c], -1)
            else:
                temp += 1
            last_ind[c] = j
            bit._add(j, 1)

        pr = r
        res[qi] = temp - bit._get_sum(l-1)

    return res














import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':
    N,Q = map(int,readline().split())
    C = list(map(int,readline().split()))

    m = map(int,read().split())
    queries = list(zip(m,m))

    print(*solve(C,queries), sep='\n')

Solution (Python):

class BIT:
    
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, Q = map(int, input().split())
c = list(map(int, input().split()))
q = []
for k in range(Q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  q.append([l, r, k])


q.sort(key = lambda x: x[1])
ans = [0 for k in range(Q)]


good = BIT(N)
lastapp = [-1 for _ in range(N)]
end = -1
for k in range(Q):
  l = q[k][0]
  r = q[k][1]
  a = q[k][2]
  for j in range(r, end, -1):
    if lastapp[c[j]-1] == -1:
      lastapp[c[j]-1] = j
      good.add(j+1, 1)
    elif lastapp[c[j]-1] < j:
      good.add(lastapp[c[j]-1]+1, -1)
      good.add(j+1, 1)
      lastapp[c[j]-1] = j
  ans[a] = good.sum(r+1) - good.sum(l)
  end = r
  
for k in range(Q):
  print(ans[k])

Solution (Python):
from sys import stdin

 
readline = stdin.readline
 
N, Q = map(int, readline().split()) 
C = list(map(int, readline().split())) 
S = [list(map(int, readline().split())) for _ in range(Q)] 

def main(N, Q, C, S):    
  
  
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): 
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) 
    return res_sum
  def BIT_update(idx,x): 
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) 
    return
 
  loc = [0 for _ in range(N)] 
  S = [(S[i], i) for i in range(Q)] 
  S.sort(key = lambda s: s[0][1]) 
  
  
  ans = [0 for _ in range(Q)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: 
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0][1] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0][1] == j+1: 
      ans[S[k][1]] = t - BIT_query(S[k][0][0]-1)
      k += 1
    if k == len(S):
      break
  return ans
 
ans = main(N, Q, C, S)
for a in ans:
  print(a)

Solution (Python):
class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < len(self.data):
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right



def solve(C, queries):
    N = len(C)
    bit = BinaryIndexedTree(N)

    last_ind = [None]*(5*10**5 + 1)

    queries = sorted(((r,l-1,i) for i,(l,r) in enumerate(queries)), key=lambda x:x[0])
    qi = 0

    res = [None]*len(queries)

    for i,c in enumerate(C):
        li = last_ind[c]
        if li is not None:
            bit[li] -= 1
        last_ind[c] = i
        bit[i] += 1

        while qi < len(queries) and queries[qi][0] == i+1:
            res[queries[qi][2]] = bit[queries[qi][1]:i+1]
            qi += 1
        if qi == len(queries):
            break

    return res

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':
    N,Q = map(int,readline().split())
    C = list(map(int,readline().split()))

    m = map(int,read().split())
    queries = list(zip(m,m))

    print(*solve(C,queries), sep='\n')

Solution (Python):
from sys import stdin


readline = stdin.readline

N, Q = map(int, readline().split()) 
C = list(map(int, readline().split())) 
S = [list(map(int, readline().split())) for _ in range(Q)] 

def main(N, Q, C, S):    
  
  
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): 
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) 
    return res_sum
  def BIT_update(idx,x): 
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) 
    return

  loc = [0 for _ in range(N)] 
  S = [(S[i], i) for i in range(Q)] 
  S.sort(key = lambda s: s[0][1]) 
  
  
  ans = [0 for _ in range(Q)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: 
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0][1] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0][1] == j+1: 
      ans[S[k][1]] = t - BIT_query(S[k][0][0]-1)
      k += 1
    if k == len(S):
      break
  return ans

ans = main(N, Q, C, S)
print(*ans, sep='\n')

Solution (Python):

class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.size = size+1
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < self.size:
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right



def solve(C, queries):
    N = len(C)
    Q = len(queries)
    bit = BinaryIndexedTree(N)

    last_ind = [None]*(N + 1)
    queries = sorted(((r,l-1,i) for i,(l,r) in enumerate(queries)), key=lambda x:x[0])

    res = [None]*Q
    pr = 0
    for r,l,i in queries:
        for j in range(pr,r):
            c = C[j]
            if last_ind[c] is not None:
                bit._add(last_ind[c], -1)
            last_ind[c] = j
            bit._add(j, 1)
        res[i] = bit._get_sum(r)-bit._get_sum(l)
        pr = r

    return res











import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':
    N,Q = map(int,readline().split())
    C = list(map(int,readline().split()))

    m = map(int,read().split())
    queries = list(zip(m,m))

    print(*solve(C,queries), sep='\n')

Solution (Python):

class BIT:
    '''
    All methods use 0-based index while the implementation use 1-based index
    '''
    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N
    
    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            i += i & (-i)
    
    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            i -= i & (-i)
        return res
    
    def sum_in(self, l, r): 
        return self.sum_to(r) - self.sum_to(l - 1)
    
    
class Query:
    def __init__(self, i, l, r):
        self.i = i
        self.l = l
        self.r = r
    
    
N, Q = map(int, input().split())
C = list(map(int, input().split()))
    
queries = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    queries[r].append(Query(i, l, r))
    
bit = BIT(N)
last = [-1] * (max(C) + 1)
    
query_idx = 0
ans = [-1] * Q
for i, c in enumerate(C):
    if last[c] != -1:
        bit.add_at(last[c], -1)    
    bit.add_at(i, +1)
    last[c] = i
    
    for q in queries[i]:
        ans[q.i] = bit.sum_in(q.l, q.r)
    
print('\n'.join(map(str, ans)))

Solution (Python):
import sys
import numpy as np


def addBIT(itemCount, items, i, value):
	while i <= itemCount:
		items[i] += value
		i += (i & (-i))

def sumFromStart(items, end):
	summary = 0
	i = end
	while i > 0:
		summary += items[i]
		i -= (i & (-i))
	return summary

def sumBIT(items, start,end):
	summary = sumFromStart(items, end) - sumFromStart(items, start-1)
	return summary




def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	
	ans=np.zeros(Q, dtype=np.int64)
	
	
	qindex = 0

	for n in range(N):
		

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			
			
			
			addBIT(N,bitArray,mostRightColorIndex[C[n]], -1 )

		
		mostRightColorIndex[C[n]] = n+1
		addBIT(N,bitArray,n+1, 1)

		
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sumBIT(bitArray,start,end)
			
			qindex += 1

	return ans

if sys.argv[-1]=='ONLINE_JUDGE':
	from numba import njit
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('addBIT','(i8,i8[:],i8,i8)')(addBIT)
	addBIT=njit(addBIT)
	cc.export('sumFromStart','(i8[:],i8)')(sumFromStart)
	sumFromStart=njit(sumFromStart)
	cc.export('sumBIT','(i8[:],i8,i8)')(sumBIT)
	sumBIT=njit(sumBIT)
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	
	cc.compile()
	exit(0)
from my_module import main,addBIT,sumBIT





def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)



queries=np.empty((Q,2),int)


for q in range(Q):
	l,r=map(int,input().split())
	
	queries[q][0] = l
	queries[q][1] = r
	



orderByR=np.argsort(queries[:,1])


mostRightColorIndex = np.zeros(N+1, int)

bitArray=np.zeros(N+1,int)

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

Solution (Python):
import sys
import numpy as np





def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	
	ans=np.zeros(Q, dtype=np.int64)
	
	
	qindex = 0

	for n in range(N):
		

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			
			
			
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			
			qindex += 1

	return ans

if sys.argv[-1]=='ONLINE_JUDGE':
	from numba import njit
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	main=njit(main, cache=True)
	cc.compile()
	exit(0)
from my_module import main





def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)



queries=np.empty((Q,2),int)


for q in range(Q):
	l,r=map(int,input().split())
	
	queries[q][0] = l
	queries[q][1] = r
	



orderByR=np.argsort(queries[:,1])


mostRightColorIndex = np.zeros(N+1, int)

bitArray=np.zeros(N+1,int)

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

Solution (Python):
import sys
import numpy as np





def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	
	ans=np.zeros(Q, dtype=np.int64)
	
	
	qindex = 0

	for n in range(N):
		

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			
			
			
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			
			qindex += 1

	return ans

if sys.argv[-1]=='ONLINE_JUDGE':
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	cc.compile()
	exit(0)
from my_module import main





def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)



queries=np.empty((Q,2),int)


for q in range(Q):
	l,r=map(int,input().split())
	
	queries[q][0] = l
	queries[q][1] = r
	



orderByR=np.argsort(queries[:,1])


mostRightColorIndex = np.zeros(N+1, int)

bitArray=np.zeros(N+1,int)

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

Solution (Python):
import sys
import numpy as np





def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	
	ans=np.zeros(Q, dtype=np.int64)
	
	
	qindex = 0

	for n in range(N):
		

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			
			
			
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			
			qindex += 1

	return ans

if sys.argv[-1]=='ONLINE_JUDGE':
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	cc.compile()
	exit(0)

from numba import njit
main=njit('i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])', cache=True)(main)



def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)



queries=np.empty((Q,2),int)


for q in range(Q):
	l,r=map(int,input().split())
	
	queries[q][0] = l
	queries[q][1] = r
	



orderByR=np.argsort(queries[:,1])


mostRightColorIndex = np.zeros(N+1, int)

bitArray=np.zeros(N+1,int)

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

Solution (Python):
import sys
import numpy as np





def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	
	ans=np.zeros(Q, dtype=np.int64)
	
	
	qindex = 0

	for n in range(N):
		

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			
			
			
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			
			qindex += 1

	return ans

if sys.argv[-1]=='ONLINE_JUDGE':
	from numba import njit
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	main=njit(main)
	cc.compile()
	exit(0)
from my_module import main



def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)



queries=np.empty((Q,2),int)


for q in range(Q):
	l,r=map(int,input().split())
	
	queries[q][0] = l
	queries[q][1] = r
	



orderByR=np.argsort(queries[:,1])


mostRightColorIndex = np.zeros(N+1, int)

bitArray=np.zeros(N+1,int)

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

Solution (Python):
import sys
import numpy as np





def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	
	ans=np.zeros(Q, dtype=np.int64)
	
	
	qindex = 0

	for n in range(N):
		

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			
			
			
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			
			qindex += 1

	return ans

if sys.argv[-1]=='ONLINE_JUDGE':
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	cc.compile()
	exit(0)
from my_module import main



def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)



queries=np.empty((Q,2),int)


for q in range(Q):
	l,r=map(int,input().split())
	
	queries[q][0] = l
	queries[q][1] = r
	



orderByR=np.argsort(queries[:,1])


mostRightColorIndex = np.zeros(N+1, int)

bitArray=np.zeros(N+1,int)

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

Solution (Python):
import sys
import numpy as np
from numba import njit


def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)



queries=np.empty((Q,2),int)


for q in range(Q):
	l,r=map(int,input().split())
	
	queries[q][0] = l
	queries[q][1] = r
	



orderByR=np.argsort(queries[:,1])


mostRightColorIndex = np.zeros(N+1, int)

bitArray=np.zeros(N+1,int)

@njit(cache=True)


def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	
	
	ans=[0]*Q
	
	qindex = 0

	for n in range(N):
		

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			
			
			
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			
			qindex += 1

	return ans

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

Solution (Python):
import sys
import numpy as np
from numba import njit,i8


def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)



queries=np.empty((Q,2),int)


for q in range(Q):
	l,r=map(int,input().split())
	
	queries[q][0] = l
	queries[q][1] = r
	



orderByR=np.argsort(queries[:,1])


mostRightColorIndex = np.zeros(N+1, int)

bitArray=np.zeros(N+1,int)

@njit(cache=True)


def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	
	ans=np.zeros(Q, i8)
	
	
	qindex = 0

	for n in range(N):
		

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			
			
			
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			
			qindex += 1

	return ans

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

Solution (Python):
import sys
import numpy as np
from numba import jit,i8 


def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)



queries=np.empty((Q,2),int)


for q in range(Q):
	l,r=map(int,input().split())
	
	queries[q][0] = l
	queries[q][1] = r
	



orderByR=np.argsort(queries[:,1])


mostRightColorIndex = np.zeros(N+1, int)

bitArray=np.zeros(N+1,int)



@jit(i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:]))
def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	
	ans=np.zeros(Q, i8)
	
	
	qindex = 0

	for n in range(N):
		

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			
			
			
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			
			qindex += 1

	return ans

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

Solution (Python):
import sys
from operator import add


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))

    P = [[] for _ in range(N)]
    for i, c in enumerate(C):
        P[c - 1].append(i)

    right = [0] * N
    for p in P:
        if len(p):
            right[p.pop()] = 1
    seg = SegmentTree(right, add, 0)

    query = [[] for _ in range(N)]
    for i, s in enumerate(sys.stdin.readlines()):
        l, r = map(int, s.split())
        query[r - 1].append((l - 1, i))

    ans = [None] * Q

    cur = N - 1
    for r, q in enumerate(reversed(query)):
        r = (N - 1) - r
        while q:
            l, i = q.pop()
            while r < cur:
                c = C[cur] - 1
                p = P[c]
                if len(p):
                    seg.update(p.pop(), 1)
                cur -= 1
            tmp = seg.get(l, r + 1)
            ans[i] = tmp

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


if __name__ == '__main__':
    main()