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

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from operator import itemgetter

    class BinaryIndexTree:
        def __init__(self, n):
            self.size = n
            self._container = [0] * (n + 1)
            self.depth = n.bit_length()

        def sum(self, i):
            if i == 0:
                return 0
            s = 0
            while i > 0:
                s += self._container[i]
                i -= i & (-i)
            return s

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

        def lower_bound(self, x):
            if x == 0:
                return 0

            s = 0
            idx = 0
            for i in range(self.depth, -1, -1):
                k = idx + (1 << i)
                if k <= self.size and s + self._container[k] < x:
                    s += self._container[k]
                    idx += 1 << i
            return idx + 1

        def __repr__(self):
            return str(self._container)

    n, q = map(int, readline().split())
    c = [0] + list(map(int, readline().split()))
    query = []
    for i in range(q):
        l, r = map(int, readline().split())
        query.append((l, r, i))

    query.sort(key=itemgetter(1))
    idx = dict()
    cur = 0
    bit = BinaryIndexTree(n)
    res = [0] * q
    s = 0
    for i in range(q):
        l, r, j = query[i]
        while cur < r:
            cur += 1
            color = c[cur]
            if idx.get(color):
                bit.add(idx[color], -1)
            else:
                s += 1
            bit.add(cur, 1)
            idx[color] = cur
        res[j] = s - bit.sum(l - 1)

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
	import sys
	input=sys.stdin.readline
	n,q=map(int,input().split())
	c=list(map(int,input().split()))
	ab=[[]for i in range(n)]
	lr=[[]for i in range(n)]
	num=[-1]*n
	for i in range(n):
		if num[c[i]-1]!=-1:
			ab[num[c[i]-1]].append(i)
		num[c[i]-1]=i
	for i in range(q):
		l,r=map(int,input().split())
		lr[l-1].append((r-1,i))
	ans=[-1]*q
	BIT=[0]*n
	for i in range(n-1,-1,-1):
		for x in ab[i]:
			x+=1
			while x<=n:
				BIT[x-1]+=1
				x=x+(x&-x)
		for x,y in lr[i]:
			X=x
			x+=1
			ret=0
			while x!=0:
				ret+=BIT[x-1]
				x=x-(x&-x)
			ans[y]=X-i+1-ret
	for x in ans:
		print(x)
if __name__ == '__main__':
	main()

Solution (Python):

from collections import defaultdict
import sys


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


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

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

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

    def get(self, i, j):
        
        return self.to_sum(j)-self.to_sum(i-1)


que = []
color_data = defaultdict(list)

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

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

que.sort(key=lambda x: x[-1])

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

for i, v in enumerate(C):
    color_data[v].append(i+1)

for key in color_data.keys():
    D = color_data[key]
    for i in range(1, len(D)):
        previous_color[D[i]] = D[i-1]

bit_tree = BIT(N)
i0, l0, r0 = que[0]

for _ in range(1, r0+1):
    bit_tree.add(_, 1)
    prev = previous_color[_]
    if prev > 0:
        bit_tree.add(prev, -1)
    ans[i0] = bit_tree.get(l0, r0)

for _ in range(1, Q):
    i, l, r = que[_]
    prv_r = que[_-1][-1]
    for j in range(prv_r+1, r+1):
        bit_tree.add(j, 1)
        prev = previous_color[j]
        if prev > 0:
            bit_tree.add(prev, -1)
    ans[i] = bit_tree.get(l, r)

for x in ans:
    print(x)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.tree = [0]*(n+1)
            self.size = n
        
        def add(self,i,x):
            while i <= self.size:
                self.tree[i] += x
                i += i&-i
        
        def sum(self,i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            return s

    N,Q = map(int,input().split())
    bit = BIT(N)
    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
    
    colorMemo = [0]*(N+1)
    cur = 1
    for q in query:
        l,r,j = q
        
        for i in range(cur,r+1):
            c = C[i-1]
            if colorMemo[c]:
                bit.add(colorMemo[c],-1)
            bit.add(i,1)
            colorMemo[c] = i
        cur = r + 1
        ans[j]=bit.sum(r)-bit.sum(l-1)

    for a in ans:
        print(a)
main()

Solution (Python):
from collections import defaultdict
import sys
def input(): return sys.stdin.readline().rstrip()
N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0 for i in range(Q)]
que = []
for i in range(Q):
    l, r = map(int, input().split())
    que.append((i, l, r))

Que = que.copy()

Que.sort(key=lambda x: x[-1])
point_data = defaultdict(list)

before_node = [-1 for i in range(N+1)]
for i, v in enumerate(C):
    if point_data[v]:
        before_node[i+1] = point_data[v][-1]
    point_data[v].append(i+1)




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

    def Sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= (i & -i)
        return s

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

    def get(self, i, j):
        return self.Sum(j)-self.Sum(i-1)


ftree = BIT(N)
for i in range(Q):
    querie, l, r = Que[i]
    if i == 0:
        for j in range(1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    else:
        for j in range(Que[i-1][-1]+1, r+1):
            ftree.add(j, 1)
            if before_node[j] > 0:
                ftree.add(before_node[j], -1)
    ans[querie] = ftree.get(l, r)
    
for i in range(Q):
    print(ans[i])

Solution (Python):
class BinaryIndexedTree(object):
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)

    def bit_add(self, index, num):
        while (index <= self.N):
            self.bit[index] += num
            index += index & -index
        return

    def bit_sum(self,index):
        result = 0
        while (index > 0):
            result += self.bit[index]
            index -= index & -index
        return result

    def bit_sum_range(self, l, r):
        if (l == r):
            return 1
        else:
            return self.bit_sum(r) - self.bit_sum(l - 1)

def main():
    from sys import stdin
    N, Q = list(map(int, input().split()))
    c = list(map(int, input().split()))
    readline = stdin.readline
    query = [list(map(int, readline().split())) + [i] for i in range(Q)]
    query_result = [0 for i in range(Q)]
    collar_pos = [-1] * (N + 1)
    bit = BinaryIndexedTree(N)

    sorted_query = sorted(query, key=lambda query: query[1])

    index = 1
    for query in sorted_query:
        l, r, q = query
        while (index <= r):
            
            if (collar_pos[c[index-1]] != -1):
                bit.bit_add(collar_pos[c[index-1]], -1)
            bit.bit_add(index, 1)
            
            collar_pos[c[index-1]] = index
            index += 1
        query_result[q] = bit.bit_sum_range(l, r)

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

if __name__ == '__main__':
    main()

Solution (Python):

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]
class BIT:
    def __init__(self, size):
        self.size = size + 1
        self.dat = [0]*self.size

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

    
    
    def sum(self, l, r=None):
        if r is None:
            res = 0
            while l > 0:
                res += self.dat[l]
                l -= l&-l
            return res

        else:
            rres = 0
            while r > 0:
                rres += self.dat[r]
                r -= r&-r
            l -= 1
            lres = 0
            while l > 0:
                lres += self.dat[l]
                l -= l&-l
            return rres - lres


def solve():
    n,Q = LI()
    c = LI()
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = BIT(n+1)
    i = 0
    p = [None]*(n+1)
    ans = [0]*Q
    for ind,(l, r) in q:
        while i < r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                bit.add(j,-1)
            bit.add(i+1)
            p[ci] = i+1
            i += 1
        ans[ind] = bit.sum(l,r)
    for i in ans:
        print(i)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]
class BIT:
    def __init__(self, size):
        self.size = size + 1
        self.dat = [0]*self.size

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

    
    
    def sum(self, l, r=None):
        if r is None:
            res = 0
            while l > 0:
                res += self.dat[l]
                l -= l&-l
            return res

        else:
            rres = 0
            while r > 0:
                rres += self.dat[r]
                r -= r&-r

            l -= 1
            lres = 0
            while l > 0:
                lres += self.dat[l]
                l -= l&-l

            return rres - lres


def solve():
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = BIT(n+1)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                bit.add(j)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+bit.sum(l)
    for i in ans:
        print(i)
    return


if __name__ == "__main__":
    solve()

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

N, Q = map(int, input().split())
c = [int(i) for i in input().split()]
lr = [[int(i) - 1 for i in input().split()] for _ in range(Q)]

class BinaryIndexedTree() :
  def __init__(self, n) :
    self.n = 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.n :
      self.tree[i] += x
      i += i & -i

BIT = BinaryIndexedTree(N + 5)
sch = [[i, l, r] for i, (l, r) in enumerate(lr)]
sch.sort(key=lambda x: x[2])
ret = [0] * Q
last = [-1] * (N + 1)

cur = 0
for i, l, r in sch :
  while cur <= r :
    BIT.add(cur + 1, 1)
    pos = last[c[cur]]
    if pos != -1 :
      BIT.add(pos + 1, -1)
    last[c[cur]] = cur
    cur += 1
  ret[i] = BIT.sum(r + 1) - BIT.sum(l)
for r in ret :
  print(r)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


class SegmentTree:
    def segfunc(self,x,y):
        
        return x + y

    
    def __init__(self,n,init,ide_ele):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 2**(n-1).bit_length()
        self.seg = [ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1] = init[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:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+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 //= 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


n,k = m()

Seg = SegmentTree(n,[0 for i in range(n)],0)
a = l()

data = []
for i in range(k):
    po = l()
    po.append(i)
    data.append(po)

data.sort(key = lambda x:x[1])

where = [-1 for i in range(n)]
ans = [0 for i in range(k)]
left = -1
for i in range(k):
    aaa = data[i]
    aaa[0] -= 1
    aaa[1] -= 1
    if aaa[1] > left:
        for j in range(left+1,aaa[1]+1):
            popopo = a[j]-1
            if where[popopo] != -1:
                Seg.update(where[popopo],-1)
            Seg.update(j,1)
            where[popopo] = j
        left = aaa[1]
    ans[aaa[2]] = Seg.query(aaa[0],aaa[1]+1)

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

Solution (Python):
from collections import defaultdict
import sys

class BIT():
    def __init__(self, n):
        '''
        n = 要素数
        要素の添字iは 0 <= i < n となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, value):
        '''i番目の要素にvalueを加算する O(logN)'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += value
            i += i & -i

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

    def sum(self, l, r):
        '''区間[l, r)の和を求める O(logN)'''
        return self._sum(r) - self._sum(l)


input = sys.stdin.readline
N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = [tuple(map(int, input().split())) for _ in range(Q)]
query = [[] for _ in range(N)]
for i, (l, r) in enumerate(LR):
    query[l-1].append((i, r-1))

hist = defaultdict(lambda: -1)
nx = [-1] * N
for i in range(N-1, -1, -1):
    nx[i] = hist[C[i]]
    hist[C[i]] = i

bit = BIT(N)
ans = [None]*Q
for l in range(N-1,-1,-1):
    if nx[l] != -1:
        bit.add(nx[l],-1)
    for i,r in query[l]:
        ans[i] = (r-l+1) + bit.sum(l,r+1)

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

Solution (Python):
I = [int(_) for _ in open(0).read().split()]
N, Q=I[:2]
C = I[2:2 + N]
LR = I[2 + N:]
2 ** 40
2 ** 20
Query = []
for i, lr in enumerate(zip(LR[::2], LR[1::2])):
    l, r = lr
    Query += [r * 2 ** 40 + l * 2 ** 20 + i]
for i, c in enumerate(C):
    Query += [(i + 1) * 2 ** 40 + c]
Query.sort()
c_i = [-1] * (N + 1)

class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])
 
    def update(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def operate_right(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def operate_left(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def query(self, l, r):  
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)
 

ans = [0] * Q
st = SegmentTree([0] * (N + 5), lambda x,y:x+y, 0)
for q in Query:
    x, yz = divmod(q, 2 ** 40)
    y, z = divmod(yz, 2 ** 20)
    if y==0:
        if c_i[z] != -1:
            st.operate_right(c_i[z], -1)
        c_i[z] = x
        st.operate_right(x, 1)
    else:
        ans[z] = st.query(y, x + 1)
print(*ans, sep='\n')

Solution (Python):
n,q = map(int, input().split())
cs = list(map(int, input().split()))

prevs = [-1] * (n+1)

sts = [-1] * n
for i,c in enumerate(cs):
    c -= 1
    if prevs[c] != -1:
        sts[prevs[c]] = i
    prevs[c] = i

qs = [[] for i in range(n)] 
for i in range(q):
    l,r = map(int, input().split())
    l -= 1
    r -= 1
    qs[l].append((r,i))

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+10)

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

    def sum(self, x):
        cnt = 0
        while x > 0:
            cnt += self.bit[x]
            x -= x&-x
        return cnt

bit = BIT(n)
ans = [0] * q
for l in range(n-1,-1,-1):
    
    if sts[l] != -1:
        bit.add(sts[l], 1)
    for r,i in qs[l]:
        cnt = bit.sum(r)
        ans[i] = r - l + 1 - cnt

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

Solution (Python):

import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

class BIT:
    def __init__(self, n=0):
        self.n = n
        self.d = [0] * (n+1)
    
    def add(self, i, x=1):
        i = int(i+1) 
        while i <= self.n:
            self.d[i] += x
            i += i&-i 
    
    def sum(self, i=None):
        x = 0
        i = int( i+1 if not (i is None) else self.n )
        while i > 0:
            x += self.d[i]
            i -= i&-i 
        return x

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
dprint("n, q =", n, q)
dprint("c =", c)


st = [0] * (n+1)
col_last = [0] * (n+1)
for i in range(n):
    t = i + 1
    col = c[i]
    s = col_last[col]
    if s > 0:
        st[s] = t
    col_last[col] = t
dprint("st =", st)


lr = [None] * n
qs = list()
sorted_qs = list()
for i in range(q):
    l, r = list(map(int, input().split()))
    qs.append((i,l,r)) 
sorted_qs = sorted(qs, key=lambda q: q[1], reverse=True)
dprint("qs =", qs)
dprint("sorted_qs =", sorted_qs)

i_qs = 0
x = n
d = BIT(n+1)
qs_ans = [0] * len(qs)
for i_qs in range(len(sorted_qs)):
    i, l, r = sorted_qs[i_qs]
    dprint("i, l, r", i, l, r)
    while (x >= l):
        if st[x] > 0:
            d.add(st[x])
            dprint("add x(s), t =", x, st[x])
        x -= 1
    qs_ans[i] = (r-l+1)-d.sum(r)

for ans in qs_ans:
    print(ans)

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

n, q = map(int, input().split())
c = list(map(int, input().split()))
lr = []
for i in range(q):
    l, r = map(int, input().split())
    lr.append((l, r, i))


left_index_dict = {}
d = defaultdict(int)

for i, ci in enumerate(c):
    index = d[ci]
    if index in left_index_dict:
        left_index_dict[index].append(i+1)
    else:
        left_index_dict[index] = [i+1]
    d[ci] = i + 1

lr.sort(key=lambda x:x[0])

index = list(left_index_dict.keys())
index.sort()
i = 0

N = n
bit = [0] * (N+1)

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

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

ans = [0] * q

for l, r, _i in lr:
    while i < len(index) and index[i] < l:
        for j in left_index_dict[index[i]]:
            add(j, 1)
        i += 1
    ans[_i] = sum(r) - sum(l-1)

for ansi in ans:
    print(ansi)

Solution (Python):
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, q = map(int, input().split())
color = [int(i) for i in input().split()]
query = []
rli = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    query.append((l, r))
    rli[i] = (r << 40) + (l << 20) + i
rli.sort()
mask = (1 << 20) - 1
bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0

for j in range(q):
    k = rli[j]
    r = k >> 40
    l = (k >> 20) & mask
    i = k & mask
    while p < r:
        c = color[p]
        before_appeared = appeared[c]
        if before_appeared != -1:
            bit_add(bit, bn, before_appeared + 2, -1)
        bit_add(bit, bn, p + 2, 1)
        appeared[c] = p
        p += 1
    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)
print('\n'.join(map(str, ans)))

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

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = tuple(sorted(r*U+i for i, (l, r) in enumerate(LR)))
B = [0]*(n+1)
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

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

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r*U+i for i, (l, r) in enumerate(LR))
B = [0]*(n+1)
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

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

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r*U+i for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Solution (Python):
n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r*U+i for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Solution (Python):
from sys import stdin

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [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):
        
        
        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, stdin.readline().split())
c = list(map(int, stdin.readline().split()))

query = []

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

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





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

bit = BIT(N)





for i in range(N):

    bit.add(i+1,1)

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

    place[c[i]] = i

    

    while next_query < len(query) and query[next_query][2] == i+1:
        
        
        
        j,l,r = query[next_query]
        ans[j] = bit.sum(r)-bit.sum(l-1)
        next_query += 1
        
        
        
        

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

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

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

import sys
input = sys.stdin.buffer.readline

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr = []
for i in range(q):
    l, r = map(int, input().split())
    lr.append([l, r, i])
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = [-1 for _ in range(q)]
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans[lr[pos][2]] = bit.sum(r) - bit.sum(l - 1)
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
    
print(*ans, sep="\n")

Solution (Python):

class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.bit[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-1)
  def lower_bound(self,x):
    w = i = 0
    k = 1<<((self.n).bit_length())
    while k:
      if i+k <= self.n and w + self.bit[i+k] < x:
        w += self.bit[i+k]
        i += k
      k >>= 1
    return i+1

def solve():
  N, Q = map(int, input().split())
  C = list(map(int, input().split()))
  lis = [-1]*(N+1) 
  bit = BIT(N) 
  ans = [0]*Q
  A = [list(map(int, input().split()))+[i] for i in range(Q)]
  A.sort(key=lambda x:x[1])
  now = 0
  for l,r,ind in A:
    for i in range(now,r):
      if lis[C[i]]>=0:
        bit.add(lis[C[i]]+1,-1)
      lis[C[i]] = i
      bit.add(i+1,1)
    ans[ind] = bit.get(l,r)
    now = r
  return ans
print(*solve(),sep='\n')

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[1:]:
    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)