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 os
import sys

import numpy as np


def solve(inp):
    def bit_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def bit_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    n = inp[0]
    q = inp[1]
    ccc = inp[2:2 + n]
    lll = inp[2 + n::2] - 1
    rrr = inp[3 + n::2] - 1

    just_left = {}
    segments = []
    for i in range(n):
        c = ccc[i]
        if c in just_left:
            segments.append((i, 0, just_left[c], 0))
        just_left[c] = i

    for i in range(q):
        segments.append((rrr[i], 1, lll[i], i))

    segments.sort()
    bit = np.zeros(n + 2, dtype=np.int64)
    ans = np.zeros(q, dtype=np.int64)

    for r, tp, l, i in segments:
        if tp == 0:
            bit_add(bit, n + 2, l + 2, 1)
        else:
            base = r - l + 1
            ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))

class SegTree:
  def segfunc(self, x, y):
    return x + y
  def __init__(self, n, ide_ele, init_val):
    
    self.ide_ele = ide_ele
    
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
qs = []
for i in range(Q):
  l, r = map(int, input().split())
  qs.append((l, r, i))
qs.sort(key = lambda x: x[1])
last = [0] * (N + 1)
fwk = SegTree(N + 1, 0, last)
for i in range(qs[0][1]): last[a[i]] = i + 1
for x in last:
  if x: fwk.update(x, fwk.query(x, x + 1) + 1)

res = [0] * Q
rlast = qs[0][1]
for l, r, i in qs:
  
  if rlast == r:
    res[i] = fwk.query(l, r + 1)
  else:
    for x in range(rlast, r):
      if last[a[x]]: fwk.update(last[a[x]], fwk.query(last[a[x]], last[a[x]] + 1) - 1)
      fwk.update(x + 1, fwk.query(x + 1, x + 2) + 1)
      last[a[x]] = x + 1
    rlast = r
    res[i] = fwk.query(l, r + 1)
for r in res: print(r)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def add(self,index,x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self,index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self,value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i+step <= self.size and s + self.tree[i+step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1

N,Q = LI()
c = LI()
l,r = LIR(Q,2)

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

bit = BIT(N)

ans = [0]*Q
last = [-1]*(N+1)
right = -1 
for i in range(Q):
    for j in range(right+1,x[i][2]):
        bit.add(j+1,1)
        if last[c[j]] != -1:
            bit.add(last[c[j]]+1,-1)
        last[c[j]] = j
    right = x[i][2]-1
    ans[x[i][0]] = bit.sum(x[i][2]) -  bit.sum(x[i][1]-1)

for a in ans:
    print(a)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 

class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]
    
    def query(self, i, j):
        
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j 
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: 
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: 
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result
    
    @property
    def data(self):
        return self.seg_data[self.N-1:self.N-1+self.n]


N, Q = map(int, readline().split())
C = list(map(int, readline().split()))
data = list(map(int,read().split()))
lr = [[i, data[2*i], data[2*i+1]] for i in range(0, Q)]
lr.sort(key=lambda x:x[2])

ans = [0] * Q
last_appeared = [-1] * (N + 1)
st = SegmentTree([0]*N)

now = 0
for i, l, r in lr:
    l -= 1
    while now < r:
        c = C[now]
        pre_idx, last_appeared[c] = last_appeared[c], now
        if pre_idx >= 0:
            st.update(pre_idx, 0)
        st.update(now, 1)
        now += 1
    ans[i] = st.query(l, r)


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

Solution (Python):
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
n,q=NM()
c=[0]+L()
Q=[L()+[i] for i in range(q)]
Q.sort(key=lambda x:x[1])
ans=[0]*(q)
lastapp=[0 for i in range(n+1)]

No=2
while No<=n:
    No*=2
tree=[0]*(2*No)

def update(k,x):
    k+=No-1
    tree[k]=x
    while k>0:
        k=(k-1)//2
        tree[k]=tree[k*2+1]+tree[k*2+2]

def add(k,x):
    k+=No-1
    while k>=0:
        tree[k]+=x
        k=(k-1)//2

def query(l,r):
    L=l+No-1
    R=r+No-1
    s=0
    while L<=R:
        if R&1:
            s+=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s+=tree[L]
        L>>=1;R>>=1
    return s
j=1
for l,r,i in Q:
    while j<=r:
        t=c[j]
        add(lastapp[t],-1)
        add(j,1)
        lastapp[t]=j
        j+=1
    ans[i]=query(l,r)
for i in ans:
    print(i)

Solution (Python):
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush

from math import ceil, log, floor
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

























































MAX = 1000001


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 = sp()
    a = L()
    queries = []
    for i in range(q):
        l, r = sp()
        queries.append(Query(l-1, r-1, i))
    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Solution (Python):
from operator import attrgetter


MAX = 6 * 10**5



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


def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    queries = []
    for i in range(q):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        queries.append(Query(l, r, i))
    queries.sort(key=attrgetter('r'))

    answeringQueries(c, n, queries, q)


if __name__ == "__main__":
    main()

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

MAX = 1000001
  

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




t=1
for _ in range(t):
    
    n,q=map(int,input().split())
    l=list(map(int,input().split()))
    queries=[]
    for __ in range(q):
        le,ri=map(int,input().split())
        le-=1
        ri-=1
        queries.append(Query(le,ri, __))

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

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
a=tuple(map(int1,input().split()))
lr=[[0,0,i] for i in range(Q)]
for i in range(Q):
    lr[i][0],lr[i][1]=map(int1,input().split())
lr.sort(key=lambda t: t[1],reverse=1)
class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s

b=RangeBIT(N)
lastap=[-1]*N
ans=[-1]*Q
l,r,j=lr.pop()
for i,x in enumerate(a):
    if lastap[x]!=-1:
        b.add(lastap[x],lastap[x]+1,-1)
    b.add(i,i+1,1)
    lastap[x]=i
    while r==i:
        ans[j]=b.sum(l,r+1)
        if lr:
            l,r,j=lr.pop()
        else:
            l,r,j=-1,-1,-1
for x in ans:
    print(x)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f
class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        self.tot=0
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        self.tot=0
        for i,x in enumerate(seq,1):
            self.tot+=x
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, val):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += val
            i += i & -i
        self.tot+=val
    
    def find(self,k):
        if k>self.tot: return self.size
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1


def main():
    mod = 1000000007
    

    
    N, Q = map(int, input().split())
    cs = tuple(map(int, input().split())) 
    
    S = list(tuple(map(int, input().split())) for i in range(Q)) 

    bit=BIT(N)
    inds=sorted(range(Q), key=lambda k: S[k][1])
    cr=0
    la=[-1]*N
    ans=[0]*Q
    for i in inds:
        l,r=S[i]
        while cr<r:
            cr+=1
            c=cs[cr-1]
            old=la[c-1]
            if old!=-1:
                
                bit.add(old,-1)
            la[c-1]=cr
            bit.add(cr,1)
        if l>1:
            tot=bit.sum(r)-bit.sum(l-1)
        else:
            tot=bit.sum(r)
        ans[i]=tot
    printl(ans)







if __name__ == "__main__":
    main()

Solution (Python):

import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil


def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans


def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y




MAX = 1000001



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

    


n, q = map(int, input().split())
queries = []
a = list(map(int, input().split()))
for i in range(q):
    x, y = map(int, input().split())
    queries += [Query(x-1, y-1, i)]

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

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


class sumBIT():
    def __init__(self, N):
        self.N = N
        self.bit = [0 for _ in range(self.N+1)]
    
    def __str__(self):
        ret = []
        for i in range(1, self.N+1):
            ret.append(self.__getitem__(i))
        return "[" + ", ".join([str(a) for a in ret]) + "]"

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

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

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

Toask = [[] for _ in range(N+1)]
for i, (l, r) in enumerate(LR):
    Toask[l].append((r, i))

bit = sumBIT(N+3)
ans = [-1]*Q

Color = [-1]*(N+1)
for l in reversed(range(1, N+1)):
    c = C[l-1]
    if Color[c] != -1:
        last = Color[c]
        bit.add(last, -1)
    bit.add(l, 1)
    for r, ind in Toask[l]:
        ans[ind] = str(bit[r])
    Color[c] = l

print("\n".join(ans))

Solution (Python):
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    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

import sys
input = sys.stdin.readline
from collections import defaultdict
n,q = map(int,input().split())
a = list(map(int,input().split()))
lr = [tuple(map(int,input().split()))+(i,) for i in range(q)]
ans = [0]*q
lr.sort(key = lambda x:x[1])
bit = Bit(n+2)
dc = defaultdict(int)
cnt = 0
for L,R,p in lr:
  L -= 1
  for i in range(cnt,R):
    if dc[a[i]]:
      l = dc[a[i]]-1
      r = i
      bit.add(l+2,1)
      bit.add(r+2,-1)
    else:
      bit.add(1,1)
      bit.add(i+2,-1)
    dc[a[i]] = i+1
  ans[p] = bit.sum(L+1)
  cnt = R
print(*ans,sep="\n")

Solution (Python):
class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

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((l,r,i))

query.sort(key=lambda x:-x[1])
ans=[0]*Q
last=[0 for i in range(N)]
B=BIT(N)
for i in range(N):
    val=c[i]-1
    if last[val]!=0:
        B.update(last[val],-1)
    last[val]=i+1
    B.update(i+1,1)
    while query and query[-1][1]==i+1:
        l,r,id=query.pop()
        res=B.query(r)-B.query(l-1)
        ans[id]=res

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

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

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

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

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


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


bit = BIT(n)
memo = {}
ans = [0] * q
query = sorted(query, key=itemgetter(1))
ind = 0

for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

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

Solution (Python):
n, q = map(int, input().split())
bit = [0] * (n + 4)


def add(a, i):
    while i <= n:
        bit[i] += a
        i += i & -i


def query(i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i & -i
    return res


a = list(map(int, input().split()))
la = [-1] * n
li = [list(map(int, input().split())) + [_] for _ in range(q)]
li.sort(key=lambda x: x[1])
idx = 0
ans = [0] * q
for l, r, xxx in li:
    l -= 1
    for i in range(idx, r):
        if la[a[i] - 1] == -1:
            add(1, i + 1)
        else:
            add(-1, la[a[i] - 1] + 1)
            add(1, i + 1)
        la[a[i] - 1] = i
    idx = r
    ans[xxx] = query(r) - query(l)
for res in ans:
    print(res)