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):
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal 
from functools import lru_cache





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):  
        self.el[i]+=x
        while i<= self.n:
            self.data[i]+= x
            i+= i&-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()))
C=[i-1 for i in C]  
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    l-=1;r-=1
    Q.append([i,l,r])
Q=sorted(Q, key=lambda x:x[2]) 
ANS=[-1]*q

B=BIT(n)
YOI=[-1]*n 
for i in range(Q[0][2],-1,-1):
    if YOI[C[i]]==-1:
        YOI[C[i]]=i
        B.add(i+1,1)


ANS[Q[0][0]]= B.sum(Q[0][2]+1)- B.sum(Q[0][1])
left=Q[0][1]; right=Q[0][2]


for l in Q:
    newleft,newright=l[1],l[2]
    for i in range(newright,right,-1):
        if YOI[C[i]]==-1: 
            YOI[C[i]]=i
            B.add(i+1, 1)
        elif YOI[C[i]]>i:
            continue
        else:
            B.add(YOI[C[i]]+1, -1)
            YOI[C[i]]=i
            B.add(i+1, 1)
    ANS[l[0]]= B.sum(newright+1)- B.sum(newleft)
    right=newright
    
for i in ANS:
    print(i)

Solution (Python):
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal 
from functools import lru_cache





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):  
        self.el[i]+=x
        while i<= self.n:
            self.data[i]+= x
            i+= i&-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()))
C=[i-1 for i in C]  
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    l-=1;r-=1
    Q.append([i,l,r])
Q=sorted(Q, key=lambda x:x[2]) 
ANS=[-1]*q

B=BIT(n)
YOI=[-1]*n 









right=-1
for l in Q:
    newleft,newright=l[1],l[2]
    for i in range(newright,right,-1):
        if YOI[C[i]]==-1: 
            YOI[C[i]]=i
            B.add(i+1, 1)
        elif YOI[C[i]]>i:
            continue
        else:
            B.add(YOI[C[i]]+1, -1)
            YOI[C[i]]=i
            B.add(i+1, 1)
    ANS[l[0]]= B.sum(newright+1)- B.sum(newleft)
    right=newright
    
for i in ANS:
    print(i)

Solution (Python):
def main(N,Q,C,LR,A):
    data = [0]*(N+1)
    def add(i,x):
        i+=1
        while i <= N:
            data[i]+= x
            i+=i&-i 
            
            
    def sum(a,b):
        r=0
        i=b
        while i>0:
            r+=data[i]
            i-=i&-i
        i=a
        while i>0:
            r-=data[i]
            i-=i&-i
        return r
    p=[-1]*N
    q=0
    a=[0]*Q
    for i in range(N):
        if p[C[i]-1]>=0:
            add(p[C[i]-1],-1)
        p[C[i]-1]=i
        add(i,1)
        while q<Q and LR[A[q]][1]==i+1:
            a[A[q]]=sum(LR[A[q]][0]-1,LR[A[q]][1])
            q+=1
    return a

import sys
if sys.argv[-1]=='ONLINE_JUDGE':
    from numba import*
    from numba.pycc import CC
    cc = CC('my_module')
  
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return njit(f)
  
    main=cc_export(main,(i8,i8,i8[:],i8[:,:],i8[:]))
    cc.compile()
    exit()
  
def input(): return sys.stdin.buffer.readline()
N,Q=map(int, input().split())
import numpy as np
C=np.array(input().split(),dtype=np.int64)

LR_ = [0] * (Q*2)
for i in range(Q):
    LR_[i*2],LR_[i*2+1] = input().split()
LR=np.array(LR_, dtype=np.int64).reshape(Q,2)

A=np.argsort(LR[:,1])

from my_module import main
print(*main(N,Q,C,LR,A),sep='\n')

Solution (Python):
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 

 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp(True)
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (510000)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            if mp[da[now]]!=-1:
                fw.add(mp[da[now]], -1)
            mp[da[now]] = now
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

    print '\n'.join(map(str, ans))



my_main()

Solution (Python):
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 

 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (n+5)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            try:
                if mp[da[now]]!=-1:
                    fw.add(mp[da[now]], -1)
                mp[da[now]] = now
            except:
                pass
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

    print '\n'.join(map(str, ans))


            

 
 
 
 
my_main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    class BIT:
        '''
        0-indexed
        '''
        def __init__(self, N):
            self.size = N
            self.tree = [0] * (N + 1)
            self.depth = N.bit_length()

        def _bitsum(self, i):
            ret = 0
            while i:
                ret += self.tree[i]
                i ^= i & -i
            return ret

        
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        
        def add(self, i, x):
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            v = 1 << self.depth
            for i in range(self.depth, -1, -1):
                k = pos + v
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += v
                v >>= 1
            return pos + 1, sum_

    
    N,Q=MI()
    C=LI()
    
    Query =[]
    
    M=10**6
    M2=10**12
    for i in range(Q):
        l, r = MI()
        l-=1
        r-=1
        Query.append(r*M2 + l*M + i)
    Query.sort()
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N+3)
    dd=[N+3]*(N+1)
    
    ans=[0]*Q
    pre=-1
    for q in Query:
        r = q // 10 ** 12
        l = (q % 10 ** 12) // 10 ** 6
        i = q % 10 ** 6
        for j in range(pre+1,r+1):
            c=C[j]
            old=dd[c]
            bit.add(old,-1)
            
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for a in ans:
        print(a)
main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    class BIT:
        '''
        0-indexed
        '''
        def __init__(self, N):
            self.size = N
            self.tree = [0] * (N + 1)
            self.depth = N.bit_length()

        def _bitsum(self, i):
            ret = 0
            while i:
                ret += self.tree[i]
                i ^= i & -i
            return ret

        
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        
        def add(self, i, x):
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            v = 1 << self.depth
            for i in range(self.depth, -1, -1):
                k = pos + v
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += v
                v >>= 1
            return pos + 1, sum_

    
    N,Q=MI()
    C=LI()
    
    Query =[]
    
    M=10**6
    M2=10**12
    for i in range(Q):
        l, r = MI()
        l-=1
        r-=1
        Query.append(r*M2 + l*M + i)
    Query.sort()
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N+3)
    dd=[N+3]*(N+1)
    
    ans=[0]*Q
    pre=-1
    for q in Query:
        r = q // 10 ** 12
        l = (q % 10 ** 12) // 10 ** 6
        i = q % 10 ** 6
        for j in range(pre+1,r+1):
            c=C[j]
            old=dd[c]
            bit.add(old,-1)
            
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for a in ans:
        print(a)
main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    def I(): return int(input())
    
    readline = sys.stdin.readline
    readall = sys.stdin.read
    MI = lambda: map(int, readline().split())
    LI = lambda: list(map(int, readline().split()))
    
    class BIT:
        '''
        0-indexed
        '''
        def __init__(self, N):
            self.size = N
            self.tree = [0] * (N + 1)
            self.depth = N.bit_length()

        def _bitsum(self, i):
            ret = 0
            while i:
                ret += self.tree[i]
                i ^= i & -i
            return ret

        
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        
        def add(self, i, x):
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            v = 1 << self.depth
            for i in range(self.depth, -1, -1):
                k = pos + v
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += v
                v >>= 1
            return pos + 1, sum_

    
    N,Q=MI()
    C=LI()
    
    Query =[]
    
    M=10**6
    M2=10**12
    for i in range(Q):
        l, r = MI()
        l-=1
        r-=1
        Query.append(r*M2 + l*M + i)
    Query.sort()
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N+3)
    dd=[N+3]*(N+1)
    
    ans=[0]*Q
    pre=-1
    for q in Query:
        r = q // 10 ** 12
        l = (q % 10 ** 12) // 10 ** 6
        i = q % 10 ** 6
        for j in range(pre+1,r+1):
            c=C[j]
            old=dd[c]
            bit.add(old,-1)
            
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for a in ans:
        print(a)
main()

Solution (Python):
SHIFT = 1 << 20


class fenwick_tree:
    """
    区間の一点更新と，区間和の取得がO(log n)で可能なデータ構造
    1-indexedで実装
    """

    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N+1)

    def sum_until(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def sum_acc(self, i, j):
        """ [i,j] の和を返す """
        return self.sum_until(j) - self.sum_until(i-1)

    def add(self, i, x):
        if i <= 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [[] for _ in range(N+1)]
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query[ri].append(le << 20 | j)

    lastappend = [-1] * (N + 1)
    bit = fenwick_tree(N)
    ans = [0]*Q

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            bit.add(lastappend[a], -1)
        lastappend[a] = i
        bit.add(i, 1)
        for le in Query[i]:
            j = le % SHIFT
            le >>= 20
            ri = i
            ans[j] = bit.sum_acc(le, ri)

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


if __name__ == '__main__':
    main()

Solution (Python):
class fenwick_tree:
    """
    区間の一点更新と，区間和の取得がO(log n)で可能なデータ構造
    1-indexedで実装
    """

    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N+1)

    def sum_until(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def sum_acc(self, i, j):
        """ [i,j] の和を返す """
        return self.sum_until(j) - self.sum_until(i-1)

    def add(self, i, x):
        if i <= 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [[] for _ in range(N+1)]
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query[ri].append((le, j))

    lastappend = [-1] * (N + 1)
    bit = fenwick_tree(N)
    ans = [0]*Q

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            bit.add(lastappend[a], -1)
        lastappend[a] = i
        bit.add(i, 1)
        for (le, j) in Query[i]:
            ri = i
            ans[j] = bit.sum_acc(le, ri)

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


if __name__ == '__main__':
    main()

Solution (Python):
class fenwick_tree:
    """
    区間の一点更新と，区間和の取得がO(log n)で可能なデータ構造
    1-indexedで実装
    """

    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N+1)

    def sum_until(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

    def sum_acc(self, i, j):
        """ [i,j] の和を返す """
        return self.sum_until(j) - self.sum_until(i-1)

    def add(self, i, x):
        if i <= 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [[] for _ in range(N+1)]
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query[ri].append((le, j))

    Query.append((-1, -1, -1))

    lastappend = [-1] * (N + 1)
    bit = fenwick_tree(N)
    ans = [0]*Q

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            bit.add(lastappend[a], -1)
        lastappend[a] = i
        bit.add(i, 1)
        for (le, j) in Query[i]:
            ri = i
            ans[j] = bit.sum_acc(le, ri)

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


if __name__ == '__main__':
    main()

Solution (Python):
class BinaryIndexedTree:
    def __init__(self, size=10**7):
        self.size = size
        self.data = [0]*(size+1)

    def add(self, index, x):
        while index <= self.size:
            self.data[index] += x
            index += index & -index

    def prefix_sum(self, index):
        res = 0
        while index >= 1:
            res += self.data[index]
            index -= index & -index
        return res
    
    def interval_sum(self, left, right):
        return self.prefix_sum(right) - self.prefix_sum(left-1)

    def __getitem__(self, index):
        return self.sum(index) - self.sum(index-1)

    
    
    
    

def main():
    from sys import stdin
    input = lambda: stdin.readline()
    LMIIS = lambda: list(map(int,input().split()))


    N,Q = LMIIS()
    
    C = [0] + LMIIS()

    
    queries = []
    for i in range(N+1):
        queries.append([])

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

    
    good_ball_places = [0] * (N+1)

    
    good_ball_exists = BinaryIndexedTree(N)

    
    k = 0
    
    out = [0] * Q
    for r,query in enumerate(queries):
        for l,order in query:
            for i in range(k+1,r+1):
                
                color = C[i]
                
                before = good_ball_places[color]
                
                if 0 < before:
                    good_ball_exists.add(before,-1)
                
                good_ball_places[color] = i
                
                good_ball_exists.add(i,1)
            
            k = r
            
            out[order] = good_ball_exists.interval_sum(l,r)
    print('\n'.join(map(str,out)))


        








    
main()

Solution (Python):
class BinaryIndexedTree:
    def __init__(self, size=10**7):
        self.size = size
        self.data = [0]*(size+1)

    def add(self, index, x):
        while index <= self.size:
            self.data[index] += x
            index += index & -index

    def prefix_sum(self, index):
        res = 0
        while index >= 1:
            res += self.data[index]
            index -= index & -index
        return res
    
    def interval_sum(self, left, right):
        return self.prefix_sum(right) - self.prefix_sum(left-1)

    def __getitem__(self, index):
        return self.sum(index) - self.sum(index-1)

    
    
    
    

def main():
    from sys import stdin
    input = lambda: stdin.readline()
    LMIIS = lambda: list(map(int,input().split()))


    N,Q = LMIIS()
    
    C = [0] + LMIIS()
    queries = []

    
    for i in range(Q):
        l,r = map(int,input().split())
        queries.append((i,l,r))
    
    
    queries.sort(key=lambda x: x[2])

    
    good_ball_places = [0] * (N+1)

    
    good_ball_exists = BinaryIndexedTree(N)

    
    k = 0
    
    out = [0] * Q
    for order,l,r in queries:
        for i in range(k+1,r+1):
            
            color = C[i]
            
            before = good_ball_places[color]
            
            if 0 < before:
                good_ball_exists.add(before,-1)
            
            good_ball_places[color] = i
            
            good_ball_exists.add(i,1)
        
        k = r
        
        out[order] = good_ball_exists.interval_sum(l,r)
    print('\n'.join(map(str,out)))


        








    
main()

Solution (Python):
class BinaryIndexedTree:
    def __init__(self, size=10**7):
        self.size = size
        self.data = [0]*(size+1)

    def add(self, index, x):
        while index <= self.size:
            self.data[index] += x
            index += index & -index

    def prefix_sum(self, index):
        res = 0
        while index >= 1:
            res += self.data[index]
            index -= index & -index
        return res
    
    def interval_sum(self, left, right):
        return self.prefix_sum(right) - self.prefix_sum(left-1)

    def __getitem__(self, index):
        return self.sum(index) - self.sum(index-1)

    
    
    
    

def main():
    from sys import stdin
    input = lambda: stdin.readline()
    LMIIS = lambda: list(map(int,input().split()))


    N,Q = LMIIS()
    
    C = [0] + LMIIS()
    queries = []

    
    for i in range(Q):
        l,r = map(int,input().split())
        queries.append((i,l,r))
    
    
    queries.sort(key=lambda x: x[2])

    
    good_ball_places = [0] * (N+1)

    
    good_ball_exists = BinaryIndexedTree()

    
    k = 0
    
    out = [0] * Q
    for order,l,r in queries:
        for i in range(k+1,r+1):
            
            color = C[i]
            
            before = good_ball_places[color]
            
            if 0 < before:
                good_ball_exists.add(before,-1)
            
            good_ball_places[color] = i
            
            good_ball_exists.add(i,1)
        
        k = r
        
        out[order] = good_ball_exists.interval_sum(l,r)
    print('\n'.join(map(str,out)))


        








    
main()

Solution (Python):
import os
import sys
import numpy as np

def proc(C, L, R, Order, N, Q):
    pl = pr = 0
    ans = 0
    A = np.zeros(N+1, dtype=np.int32)
    Ans = np.zeros(Q, dtype=np.int32)
    for idx_LR in Order:
        l = L[idx_LR]
        r = R[idx_LR]
        while pr < r:
            pr += 1
            c = C[pr]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pl > l:
            pl -= 1
            c = C[pl]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pr > r:
            c = C[pr]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pr -= 1
        while pl < l:
            c = C[pl]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pl += 1
        Ans[idx_LR] = ans
    return Ans



numba_config = [
    [proc, "i4[:](i4[:],u4[:],u4[:],i8[:],i4,i4)"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)



def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    C = np.empty(N+1, dtype=np.int32)
    C[0] = 0
    C[1:] = np.array(input().split(), dtype=np.int32)
    LR = np.array(sys.stdin.buffer.read().split(), dtype=np.uint32)
    L = LR[::2]
    R = LR[1::2]
    B = L>>9<<20|R
    Idx = (L>>9&1).astype(np.bool)
    B[Idx] = L[Idx]>>9<<20|(1<<20)-R[Idx]
    Order = np.argsort(B)
    Ans = proc(C, L, R, Order, N, Q)
    print("\n".join(map(str, Ans.tolist())))

main()

Solution (Python):
from sys import stdin
input = stdin.readline
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[2])
ans = [0 for i in range(q)]

def segfunc(x,y):
    return x + y

def init(init_val):
    
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


ide_ele = 0 
num = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
count = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball: 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    pre_r = r + 1
    ans[index] = query(l, r+1)
for i in range(q):
    print(ans[i])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)
        self.b = 1 << N.bit_length() - 1

    
    def add(self, a, w):
        x = a
        while(x <= self.N):
            self.bit[x] += w
            x += x & -x

    def get(self, a):
        ret, x = 0, a - 1
        while(x > 0):
            ret += self.bit[x]
            x -= x & -x
        return ret

    
    def cum(self, l, r):
        return self.get(r) - self.get(l)

    def lowerbound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.b
        while k > 0:
            if x + k <= self.N and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x + 1



N, Q = getNM()
C = getList()
que = [getList() for i in range(Q)]


que_d = defaultdict(list)
for i in range(Q):
    que_d[que[i][1]].append([que[i][0], i])
ans = [0] * Q

dic = defaultdict(lambda: -float('inf'))
bit = BIT(N)

for i in range(N):
    
    if dic[C[i]] >= 1:
        bit.add(dic[C[i]], -1)
    
    
    dic[C[i]] = i + 1
    bit.add(dic[C[i]], 1)

    
    if len(que_d[i + 1]) > 0:
        
        for l, j in que_d[i + 1]:
            
            
            ans[j] = bit.cum(l, i + 2)

for i in ans:
    print(i)