Buggy python submission (verdict: Time Limit Exceeded):
class BinaryIndexedTree:
    def __init__(self, size=10**7):
        self.size = size
        self.data = [0]*(size+1)

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

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

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

    # def __setitem__(self, index, x):
    #     before = self.__getitem__(index)
    #     self.add(index, -before)
    #     self.add(index, x)

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N,Q = LMIIS()
    # 1-indexedにするためリストの先頭に0を追加
    C = [0] + LMIIS()
    queries = []

    # 順番と一緒にクエリを保存
    for i in range(Q):
        queries.append((i,LMIIS()))
    
    # rについてクエリをソート
    queries.sort(key=lambda x: x[1][1])

    # 玉の種類 -> 良い玉の場所
    good_ball_places = [0] * (N+1)

    # 場所 -> 良い玉が存在するなら1,しないなら0
    good_ball_exists = BinaryIndexedTree()

    #　玉の更新範囲は[0:k]
    k = 1
    # クエリの回答
    out = [0] * Q
    for j,(l,r) in queries:
        for i in range(k,r+1):
            # 位置iの玉の色
            color = C[i]
            # 色colorの良い玉の前の位置
            before = good_ball_places[color]
            # 色colorが既出なら、良い玉の場所をリセット
            if before != 0:
                good_ball_exists.add(before,-1)
            
            # 色colorの良い玉の位置はi
            good_ball_places[color] = i
            # 位置iに良い玉が存在
            good_ball_exists.add(i,1)
        out[j] = good_ball_exists.get(l,r)
    print('\n'.join(map(str,out)))


        








    
main()

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

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

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

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

    # def __setitem__(self, index, x):
    #     before = self.__getitem__(index)
    #     self.add(index, -before)
    #     self.add(index, x)

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


    N,Q = LMIIS()
    # 1-indexedにするためリストの先頭に0を追加
    C = [0] + LMIIS()
    queries = []

    # 順番と一緒にクエリを保存
    for i in range(Q):
        l,r = map(int,input().split())
        queries.append((i,l,r))
    
    # rについてクエリをソート
    queries.sort(key=lambda x: x[2])

    # 玉の種類 -> 良い玉の場所
    good_ball_places = [0] * (N+1)

    # 場所 -> 良い玉が存在するなら1,しないなら0
    good_ball_exists = BinaryIndexedTree()

    #　玉の更新済み範囲
    k = 0
    # クエリの回答
    out = [0] * Q
    for order,l,r in queries:
        for i in range(k+1,r+1):
            # 位置iの玉の色
            color = C[i]
            # 色colorの良い玉の前の位置
            before = good_ball_places[color]
            # 色colorが既出なら、前の位置での存在を消去
            if 0 < before:
                good_ball_exists.add(before,-1)
            # 色colorの良い玉の位置はi
            good_ball_places[color] = i
            # 位置iに良い玉が存在
            good_ball_exists.add(i,1)
        # 良い玉を更新した範囲
        k = r
        # [l,r]に存在する良い玉の数の合計
        out[order] = good_ball_exists.interval_sum(l,r)
    print('\n'.join(map(str,out)))


        








    
main()