Problem: You are given a sequence with N integers: A = \\{ A_1, A_2, \cdots, A_N \\}. For each of these N integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:    * If A_i and A_j (i < j) are painted with the same color, A_i < A_j.  Find the minimum number of colors required to satisfy the condition.

Submission attempts (in order):

import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left
from array import array


class BinarySearchTree:
    def __init__(self, ls: list = []):
        
        self.bst = array('q' sorted(ls))  

    
    #     return f'BST:{self.bst}'

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        
        # self.bst.insert(idx,x)
        insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        
        return bisect_right(self.bst, x)

    def find(self, x):
        
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        
        idx_del = self.bisect_right(x) + 1  
        if idx_del - 1 == len(self.bst):  
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))



import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left
from collections import deque
from array import array


class BinarySearchTree:
    def __init__(self, ls: list = []):
        
        self.bst = array(sorted(ls))  

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        idx = self.bisect_left(x)
        self.bst.insert(idx, x)
        # insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        
        return bisect_right(self.bst, x)

    def find(self, x):
        
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        
        idx_del = self.bisect_right(x) + 1  
        if idx_del - 1 == len(self.bst):  
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))



import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left
from array import array


class BinarySearchTree:
    def __init__(self, ls: list = []):
        
        self.bst = array('q', sorted(
            ls))  

    
    #     return f'BST:{self.bst}'

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        
        # self.bst.insert(idx,x)
        insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        
        return bisect_right(self.bst, x)

    def find(self, x):
        
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        
        idx_del = self.bisect_right(x) + 1  
        if idx_del - 1 == len(self.bst):  
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))


Verdicts: Runtime Error

Runtime Error

Accepted