Buggy python submission (verdict: Time Limit Exceeded):
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])

# endregion


class BinaryIndexedTree:
    def __init__(self, n):
        self.N = n
        self.bit = [0] * (n + 1)  # 1-index

    def sum(self, idx):
        """return sum(a[0]~a[idx])

        Args:
            idx (int): 1-index

        Returns:
            int: sum(a[0]+...+a[i])
        """
        res = 0
        while idx:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def add(self, idx, x):
        """a[idx]+=x

        Args:
            idx (int): 1-index
            x (int): add value
        """
        while idx <= self.N:
            self.bit[idx] += x
            idx += idx & (-idx)


n, q = inpl()
c = inpl()
query = [inpl() + [i] for i in range(q)]
query.sort(key=itemgetter(1))
rightest = [-1] * (n + 1)
now_q = 0
Bit = BinaryIndexedTree(n)
ans = [0] * q

for i in range(n):
    if rightest[c[i]] != -1:
        Bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    Bit.add(i + 1, 1)

    while now_q < q and query[now_q][1] == i + 1:
        ans[query[now_q][2]] = Bit.sum(query[now_q][1]) - Bit.sum(query[now_q][0] - 1)
        now_q += 1
print("\n".join(map(str, ans)))


Fixed submission:
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])

# endregion


class BinaryIndexedTree:
    def __init__(self, n):
        self.N = n
        self.bit = [0] * (n + 1)  # 1-index

    def sum(self, idx):
        """return sum(a[0]~a[idx])

        Args:
            idx (int): 1-index

        Returns:
            int: sum(a[0]+...+a[i])
        """
        res = 0
        while idx:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def add(self, idx, x):
        """a[idx]+=x

        Args:
            idx (int): 1-index
            x (int): add value
        """
        while idx <= self.N:
            self.bit[idx] += x
            idx += idx & (-idx)


n, q = inpl()
c = inpl()
query = [inpl() + [i] for i in range(q)]
query.sort(key=itemgetter(1))
rightest = [-1] * (n + 1)
now_q = 0
Bit = BinaryIndexedTree(n)
ans = [0] * q

for i in range(n):
    if rightest[c[i]] != -1:
        Bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    Bit.add(i + 1, 1)

    while now_q < q and query[now_q][1] == i + 1:
        ans[query[now_q][2]] = Bit.sum(query[now_q][1]) - Bit.sum(query[now_q][0] - 1)
        now_q += 1
print("\n".join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val = init_val
        # Range Minimum Query
        self.N0 = 2**(N - 1).bit_length()  # Nを超える最小の2のべき乗
        # 0-indexedで管理(N0-1からはじまる)
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res = left | right
        return res

    def update(self, k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0 - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(
                self.data[2 * k + 1], self.data[2 * k + 2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R - 1])

            if L & 1:
                s = self._segfunc(s, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s


def inttobit(i):
    return 1 << (i - 1)


def popcnt(n):
    return bin(n).count("1")


n, q = inpl()
s = [inttobit(i) for i in inpl()]
st = SegmentTree(0, n)
ans = []
for i in range(n):
    st.update(i, s[i])
for i in range(q):
    l, r = inpl()
    tmp = st.query(l - 1, r)
    ans.append(popcnt(tmp))

for i in ans:
    print(i)


Fixed submission:
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])

# endregion


class BinaryIndexedTree:
    def __init__(self, n):
        self.N = n
        self.bit = [0] * (n + 1)  # 1-index

    def sum(self, idx):
        """return sum(a[0]~a[idx])

        Args:
            idx (int): 1-index

        Returns:
            int: sum(a[0]+...+a[i])
        """
        res = 0
        while idx:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def add(self, idx, x):
        """a[idx]+=x

        Args:
            idx (int): 1-index
            x (int): add value
        """
        while idx <= self.N:
            self.bit[idx] += x
            idx += idx & (-idx)


n, q = inpl()
c = inpl()
query = [inpl() + [i] for i in range(q)]
query.sort(key=itemgetter(1))
rightest = [-1] * (n + 1)
now_q = 0
Bit = BinaryIndexedTree(n)
ans = [0] * q

for i in range(n):
    if rightest[c[i]] != -1:
        Bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    Bit.add(i + 1, 1)

    while now_q < q and query[now_q][1] == i + 1:
        ans[query[now_q][2]] = Bit.sum(query[now_q][1]) - Bit.sum(query[now_q][0] - 1)
        now_q += 1
print("\n".join(map(str, ans)))