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
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class BIT():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.UNITY_SUM = 0
        self.dat = [[self.UNITY_SUM for i in range(n + 1)] for j in range(2)]
    
    def sub_ADD(self, p, a, x):
        i = a
        while i < len(self.dat[p]):
            self.dat[p][i] = self.dat[p][i] + x
            i += i & -i
    
    def ADD(self, a, b, x):
        self.sub_ADD(0, a, x * -(a - 1))
        self.sub_ADD(1, a, x)
        self.sub_ADD(0, b, x * (b - 1))
        self.sub_ADD(1, b, x * (-1))
    
    def sub_SUM(self, p, a):
        res = self.UNITY_SUM
        i = a
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def SUM(self, a, b):
        return self.sub_SUM(0, b - 1) + self.sub_SUM(1, b - 1) * (b - 1) - self.sub_SUM(0, a - 1) - self.sub_SUM(1, a - 1) * (a - 1)
    
    def PRINT(self):
        for i in range(1, len(self.dat[0])):
            print(self.SUM(i, i + 1), end = "")
            print(",", end = "")
        print()

def main():
    N, Q = map(int,readline().split())
    C = list(map(int,readline().split()))  
    S = sys.stdin.readlines()
    lefts = [0] * Q
    rights = [0] * Q
    ids = [0] * Q
    for i in range(Q):
        lefts[i], rights[i] = map(int,S[i].split())
        lefts[i] -= 1
        ids[i] = i
    
    ids = sorted(ids, key=lambda x: rights[x])

    bit = BIT(N+5)
    prev = [-1] * 1100000
    res = [0] * Q
    r = 0
    for i in ids:
        while r < rights[i]:
            bit.ADD(prev[C[r]]+2, r+2, 1)
            prev[C[r]] = r
            r += 1
        tmp = bit.SUM(lefts[i]+1, lefts[i]+2)
        res[i] = max(res[i], tmp)
    for i in range(Q):
        print(res[i])

main()

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=np.array(sys.stdin.buffer.read().split(),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):
NN = 19
XX = [0] * (2**(NN+1)-1)

def addvalue(j, x):
    i = 2**NN + j - 1
    while i >= 0:
        XX[i] += x
        i = (i-1) // 2

def rangesum(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    s = 0
    while l < r:
        if l%2:
            s += XX[l-1]
            l += 1
        if r%2:
            r -= 1
            s += XX[r-1]
        l >>= 1
        r >>= 1
    return s

N, Q = map(int, input().split())
C = [int(a) - 1 for a in input().split()]
X = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    X[r-1].append((l - 1, i))
last = [-1] * N
ANS = [-1] * Q
addvalue(1, N)
for r in range(N):
    c = C[r]
    addvalue(last[c] + 2, -1)
    addvalue(r + 2, 1)
    last[c] = r
    for l, i in X[r]:
        ANS[i] = rangesum(l + 2, 1 << NN)
    
print(*ANS, sep = "\n")

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


class SegmentTreeSUM(object):  
    def __init__(self, size):
        self.len = 1 << (size-1).bit_length()
        
        self.array = [0 for _ in range(2 * self.len)]

    def update(self, i, x):  
        i += self.len
        while i > 0:
            self.array[i] = self.array[i] + x
            i >>= 1
        

    def get(self, i):  
        return self.array[i + self.len]

    def get_sum(self, l, r):  
        L = l+self.len
        R = r+self.len
        ANS = 0

        while L < R:
            if L & 1:
                ANS = ANS + self.array[L]
                L += 1

            if R & 1:
                R -= 1
                ANS = ANS + self.array[R]
            L >>= 1
            R >>= 1

        return ANS


N, Q = na()
c_array = na()

tree = SegmentTreeSUM(N)


q_array = []
for i in range(Q):
    l, r = na()
    q_array.append([i, l-1, r])

q_array = sorted(q_array, key=lambda x: x[2])
ans = [0] * Q
last_idx = [-1] * (N+1)
q_idx = 0
for i, c in enumerate(c_array):
    tree.update(i, 1)
    if last_idx[c] != -1:
        tree.update(last_idx[c], -1)
    last_idx[c] = i
    while(q_idx < Q and q_array[q_idx][2] == (i+1)):
        idx, l, r = q_array[q_idx]
        ans[idx] = tree.get_sum(l, r)
        q_idx += 1


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

Solution (Python):

import sys
class BinaryIndexedTree:
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size
 
    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return
 
    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res
 
    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

n, q = map(int, sys.stdin.readline().split())
c = list(map(int, sys.stdin.readline().split()))
lr = [list(map(int, sys.stdin.readline().split())) + [i] for i in range(q)]
lr.sort(key=lambda x:x[1])
BIT = BinaryIndexedTree(n+1)
LastAppeared = [-1] * (n+1)
ans = [0] * q
R = 0
for l, r, i in lr:
    while R < r:
        if LastAppeared[c[R]] != -1:
            BIT.add(LastAppeared[c[R]], -1)
        LastAppeared[c[R]] = R+1
        BIT.add(R+1, 1)
        R += 1
    ans[i] = BIT.sum(r) - BIT.sum(l-1)

for i in ans:
    print(i)

Solution (Python):
import sys
def main():
  n,q,*c=map(int,sys.stdin.buffer.read().split())
  a=[0]*q
  j,*b=t=[0]*9**6
  for i in sorted(range(q),key=lambda x:c[x+x-~n]):
    l,r=c[i+i+n],c[i+i-~n]
    while j<r:
      k=c[j]
      j+=1
      x,y,b[k]=b[k]+1,j+1,j
      while x<=n:
        t[x]+=1
        x=x+(x&-x)
      while y<=n:
        t[y]-=1
        y=y+(y&-y)
    s=0
    while l:
      s=s+t[l]
      l=l-(l&-l)
    a[i]=s
  print(' '.join(map(str,a)))
main()

Solution (Python):
from operator import itemgetter
N,Q = map(int, input().split())
C = [int(c) for c in input().split()]
L = [[int(l) for l in input().split()] for _ in range(Q)]

for i in range(Q):
    L[i].append(i)
M = pow(2, len(bin(N))-2)
BIT = [0]*(M+1)
L.sort(key=itemgetter(1))
memo = [0]*(N+1)

ans = [0]*Q
i = 1
j = 0
while i <= N:
    c = C[i-1]
    idx = i
    if i <= L[j][1]:
        if memo[c] > 0:
            k = memo[c]
            while k <= M:
                BIT[k] -= 1
                k += k&(-k)
        memo[c] = i
        while idx <= M:
            BIT[idx] += 1
            idx += idx&(-idx)
    if i == L[j][1]:
        cnt = 0
        n = L[j][1]
        while n > 0:
            cnt += BIT[n]
            n -= n&(-n)
        n = L[j][0]-1
        while n > 0:
            cnt -= BIT[n]
            n -= n&(-n)
        ans[L[j][2]] = cnt
        j += 1
        if j == Q:
            break
        elif L[j][1] == i:
            i -= 1
    i += 1

for a in ans:
    print(a)

Solution (Python):
def A(i,x):
 while i<=n:t[i]+=x;i+=i&-i
n,q,*c=map(int,open(0).read().split())
a=[0]*q
j,*b=t=[0]*9**6
for i in sorted(range(q),key=lambda x:c[x+x-~n]):
 while j<c[i+i-~n]:d=c[j];j+=1;A(b[d]+1,1);b[d]=j;A(j+1,-1)
 l=c[i+i+n]
 while l:a[i]+=t[l];l-=l&-l
print(*a)

Solution (Python):
import sys
from bisect import bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()

class BIT:

    """
    https://tjkendev.github.io/procon-library/python/range_query/bit.html
    Binary index treeの実装
    1-indexedの配列[a1, a2,...,an]に対して以下のクエリをO(logn)で行う:
        1. aiにxを加える
        2. 区間和 ai + a(i+1) + ... + aj の和を求める
    isom法を使えば、
        1. aiの値を取得する
        2. 区間[i, j]の全ての数にxを加算する
    もO(logN)で行うことができる
    """

    def __init__(self, n):
        """
        添字は1スタート
        """
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def add(self, i, x):
        """
        i>0に対してaiにxを加算(x < 0でもOK)
        """
        if i <= 0 or self.n < i:
            raise ValueError("i should be within 1 to n")
        else:
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

    def sum(self, i):
        """
        添字1からiまでの累積和を求める
        """
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i 
        return s

    def get(self, i, j=None):
        """
        添字iからjまでの累積和を求める
        j=Noneの場合はaiの値を返す
        """
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i - 1)


def main():
    """
    区間の種類数を答える問題は典型みたい。
    https://hama-du-competitive.hatenablog.com/entry/2016/10/01/001418
    ポイントはクエリをrの昇順に整理しておくこと。
    玉の各種類ごとに、それが最後にどこで出現したかをBITに記録していく。
    """
    N, Q = map(int, input().split())
    C = [0] + list(map(int, input().split()))
    queri = []
    for q in range(Q):
        l, r = map(int, input().split())
        queri.append(r * 10**12 + l * 10**6 + q)
    queri.sort()
    

    lastAppeared = [0] * (N + 1)  
    r0 = queri[0] // 10**12
    for i, c in enumerate(C):
        if i == 0: continue
        if i > r0: break
        lastAppeared[c] = i
    tree = BIT(N)
    for x in range(1, N + 1):
        if lastAppeared[x] != 0:
            tree.add(lastAppeared[x], 1)

    ans = [0] * Q
    pre_R = r0
    for x in queri:
        r, x = x // 10**12, x % 10**12
        l, q = x // 10**6, x % 10**6
        if r > pre_R:
            for i in range(pre_R + 1, r + 1):
                if lastAppeared[C[i]] != 0:
                    tree.add(lastAppeared[C[i]], -1)
                lastAppeared[C[i]] = i
                tree.add(i, 1)
        ans[q] = tree.get(l, r)
        pre_R = r
        

    for a in ans: print(a)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

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

N, Q = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = map(int, input().split())
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = [-1]*Q

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans[i] = r-x+1-bit.acc(r+1)

for ans_i in ans:
    print(ans_i)

Solution (Python):

class BinaryIndexedTree:
    def __init__(self, n):
        
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i - 1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i - 1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r - 1)
        if l: res -= self.sum(l - 1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def bisearch_fore(self, l, r, x):
        """ 区間[l, r]を左から右に向かってx番目の値がある位置 """
        l_sm = self.sum(l - 1)
        ok = r + 1
        ng = l - 1
        while ng + 1 < ok:
            mid = (ok + ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return 1<<60

def resolve():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))


    pi = [-1] * (N + 1)  
    ps = [[] for i in range(N)]

    for i in range(N):
        l = pi[A[i]]
        if l != -1:
            ps[l].append(i)
        pi[A[i]] = i

    qs = [[] for i in range(N)]
    for i in range(Q):
        l, r = map(lambda x:int(x)-1, input().split())
        qs[l].append((r, i))

    BIT = BinaryIndexedTree(N + 1)
    ans = [0] * Q

    for x in range(N - 1, -1, -1):
        for y in ps[x]:
            BIT.add(y, 1)

        for r, i in qs[x]:
            ans[i] = (r - x + 1) - BIT.sum(r)

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



if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
n,q=map(int,input().split())
a=list(map(int,input().split()))
queries=[[]for _ in[0]*n]
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[0]*n
bit=[0]*(n+1)
ans=[0]*q
for i,ai in enumerate(a):
  x=lastAppeared[ai-1]+1
  while x<=n+1:
    bit[x-1]-=1
    x+=x&-x
  x=i+2
  while x<=n+1:
    bit[x-1]+=1
    x+=x&-x
  lastAppeared[ai-1]=i+1
  for l,ind in queries[i]:
    x=i+2
    while x:
      ans[ind]+=bit[x-1]
      x-=x&-x
    x=l+1
    while x:
      ans[ind]-=bit[x-1]
      x-=x&-x
print(*ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
n,q=map(int,input().split())
a=list(map(int,input().split()))
queries=[[]for _ in[0]*n]
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[0]*n
bit=[0]*(n+1)
ans=[0]*q
for i in range(n):
  x=lastAppeared[a[i]-1]+1
  while x<=n+1:
    bit[x-1]-=1
    x+=x&-x
  x=i+2
  while x<=n+1:
    bit[x-1]+=1
    x+=x&-x
  lastAppeared[a[i]-1]=i+1
  for l,ind in queries[i]:
    x=i+2
    while x:
      ans[ind]+=bit[x-1]
      x-=x&-x
    x=l+1
    while x:
      ans[ind]-=bit[x-1]
      x-=x&-x
print(*ans)

Solution (Python):
def main():
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[[]for _ in[0]*n]
  for i in range(q):
    l,r=x[n+i*2],x[n+i*2+1]
    l-=1
    r-=1
    queries[r].append((l,i))
  lastAppeared=[0]*n
  bit=[0]*(n+1)
  ans=[0]*q
  for i in range(n):
    x=lastAppeared[a[i]-1]+1
    while x<=n+1:
      bit[x-1]-=1
      x+=x&-x
    x=i+2
    while x<=n+1:
      bit[x-1]+=1
      x+=x&-x
    lastAppeared[a[i]-1]=i+1
    for l,ind in queries[i]:
      x=i+2
      while x:
        ans[ind]+=bit[x-1]
        x-=x&-x
      x=l+1
      while x:
        ans[ind]-=bit[x-1]
        x-=x&-x
  print(*ans)

if __name__ == "__main__":
  main()

Solution (Python):
n,q,*x=map(int,open(0).read().split())
a=x[:n]
queries=[[]for _ in[0]*n]
for i in range(q):
  l,r=x[n+i*2],x[n+i*2+1]
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[0]*n
bit=[0]*(n+1)
ans=[0]*q
for i in range(n):
  x=lastAppeared[a[i]-1]+1
  while x<=n+1:
    bit[x-1]-=1
    x+=x&-x
  x=i+2
  while x<=n+1:
    bit[x-1]+=1
    x+=x&-x
  lastAppeared[a[i]-1]=i+1
  for l,ind in queries[i]:
    x=i+2
    while x:
      ans[ind]+=bit[x-1]
      x-=x&-x
    x=l+1
    while x:
      ans[ind]-=bit[x-1]
      x-=x&-x
print(*ans)

Solution (Python):
n,q=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):a[i]-=1
queries=[[]for _ in range(n)]
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[0]*n
bit=[0]*(n+1)
ans=[0]*q
for i in range(n):
  x=lastAppeared[a[i]]+1
  while x<=n+1:
    bit[x-1]-=1
    x+=x&-x
  x=i+2
  while x<=n+1:
    bit[x-1]+=1
    x+=x&-x
  lastAppeared[a[i]]=i+1
  for l,ind in queries[i]:
    x=i+2
    while x:
      ans[ind]+=bit[x-1]
      x-=x&-x
    x=l+1
    while x:
      ans[ind]-=bit[x-1]
      x-=x&-x
print(*ans)

Solution (Python):
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    
    bit = [0] * (n + 1)

    
    
    
    last_visit = [-1] * MAX

    
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        
        
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            
        
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        
        
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    n = N
    queries = []
    for i in range(Q):
        l, r = [int(x) for x in input().split()]
        queries.append(Query(l - 1, r - 1, i))
    q = Q

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Solution (Python):
import sys
from operator import add, itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k: int, x):
        k += self.N0 - 1
        
        self.data[k] = x
        
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        
        return res


def solve():
    N, Q = map(int, rl().split())
    c = list(map(lambda n: int(n) - 1, rl().split()))
    lr = [list(map(int, rl().split())) for _ in range(Q)]
    
    query = sorted([(left - 1, right, idx) for idx, (left, right) in enumerate(lr)], key=itemgetter(1))
    seg_tree = SegmentTree([0] * N, add, 0)
    c_to_idx = [-1] * N
    
    p_right = 0
    ans = [0] * Q
    for left, right, idx in query:
        for i in range(p_right, right):
            if c_to_idx[c[i]] != -1:
                seg_tree.update(c_to_idx[c[i]], 0)
            seg_tree.update(i, 1)
            c_to_idx[c[i]] = i
        p_right = right
        ans[idx] = seg_tree.query(left, right)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline

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

class BIT:
  from operator import add, sub
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res

  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))

GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  if st < Q:
    while query[st][2] == i+1:
      ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
      st += 1
      if st == Q:
        break

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

Solution (Python):
class BIT:
    """
    1-indexed
    """
    def __init__(self, size):
        self.size = size
        self.data = [0] * (size + 1)

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

    def sum(self, index):
        """
        右端含める
        """
        ret = 0
        while index:
            ret += self.data[index]
            index -= index & (-index)
        return ret

    def search(self, val):
        """
        x_1 + ... x_i >= val を満たす最小のi
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)  

        while step:
            if i + step <= self.size and s + self.data[i + step] < val:
                i += step
                s += self.data[i]
            step //= 2
        return i + 1

N, Q = map(int, input().split())
C = [-1] + list(map(int, input().split()))
tree = BIT(N)

query = [[] for _ in range(N + 1)]
for q in range(Q):
    l, r = map(int, input().split())
    query[r].append((q, l))

index = [-1] * (N + 1)
ans = [0] * Q

for r in range(1, N + 1):
    if index[C[r]] > 0:
        tree.add(index[C[r]], -1)
    tree.add(r, 1)
    index[C[r]] = r

    for q, l in query[r]:
        ans[q] = tree.sum(r) - tree.sum(l - 1)

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

Solution (Python):
"""
O_______________________________________________________________________________________________________________O
*                                                                                                               *
*                        xxxxx                                                                                  *
*                       xxxxxxx                                                 xxxxxxxxxxxxxxxxx               *
*                      xxxxxxxxx                                           xxxxxxxxxx      xxxxxxxxxxx          *
*                     xxxxx xxxxx                                      xxxxx                     xxxxxxxxxx     *
*                    xxxxx   xxxxx                                  xxxxx                             xxxxxxx   *
*                   xxxxx     xxxxx                               xxxxx                                         *
*                  xxxxx       xxxxx                             xxxxx                                          *
*                 xxxxx         xxxxx                           xxxxx                                           *
*                xxxxx           xxxxx                          xxxxx                                           *
*               xxxxx             xxxxx                        xxxxx                                            *
*              xxxxx               xxxxx                       xxxxx                                            *
*             xxxxx                 xxxxx                     xxxxx                                             *
*            xxxxxxxxxxxxxxxxxxxxxxxxxxxxx                    xxxxx                                             *
*           xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx                   xxxxx                                             *
*          xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx                   xxxxx                                            *
*         xxxxx                         xxxxx                  xxxxx                                            *
*        xxxxx                           xxxxx                  xxxxx                                           *
*       xxxxx                             xxxxx                 xxxxx                                           *
*      xxxxx                               xxxxx                 xxxxx                                          *
*     xxxxx                                 xxxxx                 xxxxx                                         *
*    xxxxx                                   xxxxx                  xxxxx                             xxxxxxx   *
*   xxxxx                                     xxxxx                    xxxxx                     xxxxxxxxxx     *
*  xxxxx                                       xxxxx                       xxxxxxxxxx      xxxxxxxxxxx          *
* xxxxx                                         xxxxx                           xxxxxxxxxxxxxxxxx               *
*                                                                                                               *
O_______________________________________________________________________________________________________________O
"""
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*q
queries=[[]for _ in range(n)]
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[-1]*n
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]-1]!=-1:
    bitt.add(lastAppeared[a[i]-1],-1)
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  for l,ind in queries[i]:
    ans[ind]=bitt.sum(l,i-1)
print(*ans)

Solution (Python):
import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

Bsize = 700

def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)

def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int64)
    ans = 0

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int64)
    nl, nr = 0, 0
    for i in ind:
        l, r = LR[i]
        l -= 1
        
        while nl > l:
            nl -= 1
            add(A[nl])
        while nr < r:
            add(A[nr])
            nr += 1
        while nl < l:
            rem(A[nl])
            nl += 1
        while nr > r:
            nr -= 1
            rem(A[nr])
        
        answers[i] = ans
    return answers

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i4 = numba.int32
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    Mo_argsort = cc_export(Mo_argsort, (i8[:,:],))
    main = cc_export(main, (i8[:], i8[:, :]))
    cc.compile()

from my_module import main

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q, 2)

ans = main(A, LR)
print('\n'.join(map(str, ans.tolist())))