Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter

class BinaryIndexedTree:  # 0-index !!!
    """
    init(n):     要素数nを与えて0で初期化
    add(i, x):   i番目の値にxを追加 O(logN)
    sum(i):      区間[0,i)の和を返す O(logN)
    query(l, r): 区間[l,r)の和を返す O(logN)
    """

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)  # 内部的には1-indexで扱う

    def add(self, i, x):  # 0-index
        i += 1  # 内部的には1-indexで扱う
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

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

    def query(self, l, r):  # 0-index  sum of [l,r)
        return self.sum(r) - self.sum(l)

# ---------------------- #

n, q = (int(x) for x in input().split())
C = list(int(x) - 1 for x in input().split())
LR = [tuple(int(x) for x in input().split()) for _ in range(q)]

bit = BinaryIndexedTree(n)
color_right_index = [-1] * n
queries = [(i, l - 1, r - 1) for i, (l, r) in enumerate(LR)]
queries.sort(key=itemgetter(2))
ANS = [0] * q
k = 0
for i, l, r in queries:
    while k <= r and k <= n:
        color = C[k]
        if color_right_index[color] != -1:
            bit.add(color_right_index[color], -1)
        color_right_index[C[k]] = k
        bit.add(k, 1)
        k += 1
    ANS[i] = bit.query(l, r + 1)

for ans in ANS:
    print(ans)


Fixed submission:
import sys
from operator import itemgetter
def input(): return sys.stdin.readline().rstrip()

class BinaryIndexedTree:  # 0-index !!!
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)  # 内部的には1-indexで扱う

    def add(self, i, x):  # 0-index
        i += 1  # 内部的には1-indexで扱う
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

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

    def query(self, l, r):  # 0-index  sum of [l,r)
        return self.sum(r) - self.sum(l)

# ---------------------- #

n, q = (int(x) for x in input().split())
C = list(int(x) - 1 for x in input().split())
LR = [tuple(int(x) for x in input().split()) for _ in range(q)]

bit = BinaryIndexedTree(n)
color_right_index = [-1] * n
queries = [(i, l - 1, r - 1) for i, (l, r) in enumerate(LR)]
queries.sort(key=itemgetter(2))
ANS = [0] * q
k = 0
for i, l, r in queries:
    while k <= r and k <= n:
        color = C[k]
        if color_right_index[color] != -1:
            bit.add(color_right_index[color], -1)
        color_right_index[C[k]] = k
        bit.add(k, 1)
        k += 1
    ANS[i] = bit.query(l, r + 1)

for ans in ANS:
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

    def show(self):
        return self.tree[self.size: self.size + self.n]

# ---------------------- #

def set_func(a, b):
    return a | b

n, q = (int(x) for x in input().split())
C = list(int(x) for x in input().split())
seq = [set() for _ in range(n)]
for i in range(n):
    seq[i].add(C[i])
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
seg = SegTree(seq, fx=set_func, ex=set())
for l, r in queries:
    l -= 1
    ans = len(seg.query(l, r))
    print(ans)


Fixed submission:
import sys
from operator import itemgetter
def input(): return sys.stdin.readline().rstrip()

class BinaryIndexedTree:  # 0-index !!!
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)  # 内部的には1-indexで扱う

    def add(self, i, x):  # 0-index
        i += 1  # 内部的には1-indexで扱う
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

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

    def query(self, l, r):  # 0-index  sum of [l,r)
        return self.sum(r) - self.sum(l)

# ---------------------- #

n, q = (int(x) for x in input().split())
C = list(int(x) - 1 for x in input().split())
LR = [tuple(int(x) for x in input().split()) for _ in range(q)]

bit = BinaryIndexedTree(n)
color_right_index = [-1] * n
queries = [(i, l - 1, r - 1) for i, (l, r) in enumerate(LR)]
queries.sort(key=itemgetter(2))
ANS = [0] * q
k = 0
for i, l, r in queries:
    while k <= r and k <= n:
        color = C[k]
        if color_right_index[color] != -1:
            bit.add(color_right_index[color], -1)
        color_right_index[C[k]] = k
        bit.add(k, 1)
        k += 1
    ANS[i] = bit.query(l, r + 1)

for ans in ANS:
    print(ans)