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
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N = int(input().strip())
    A = [int(input().strip()) for _ in range(N)]
    return N, A


@njit
def segtree_init(size, init_value=10**8, dtype=np.int32):
    
    n = 1
    while size > 1:
        size >>= 1
        n += 1
    treesize = n * 2
    st = np.full(treesize, init_value, dtype=dtype)
    st_idx = np.arange(treesize, dtype=dtype)
    offset = st.shape[0] // 2
    return st, st_idx, offset

@njit
def segtree_update(st, st_idx, offset, key, value, init_value=10**8):
    
    k = offset + key
    st[k] = value
    k >>= 1
    while k > 0:
        if st[k * 2] <= st[k * 2 + 1]:
            st[k] = st[k * 2]
            st_idx[k] = st_idx[k * 2]
        else:
            st[k] = st[k * 2 + 1]
            st_idx[k] = st_idx[k * 2 + 1]
        k >>= 1

    
@njit
def _segtree_find_le(st, st_idx, offset, value, k=1, init_value=10**8):
    
    if value < st[k]:
        return (st.shape[0], -init_value)
    elif value == st[k] or k >= offset:
        return (st_idx[k], st[k])
    else:
        li, lv = _segtree_find_le(st, st_idx, offset, value, k * 2, init_value=init_value)
        ri, rv = _segtree_find_le(st, st_idx, offset, value, k * 2 + 1,  init_value=init_value)
        mi = li if lv >= rv else ri
        mv = lv if lv >= rv else rv
        if mi < st.shape[0]:
            return (mi, mv)
        else:
            return (st.shape[0], -init_value)
    
@njit
def segtree_find_le(st, st_idx, offset, value, init_value=10**8):
    
    i, v = _segtree_find_le(st, st_idx, offset, value, k=1, init_value=init_value)
    if i == st.shape[0]:
        return (-1, init_value)
    else:
        return (i - offset, v)


def solve(N, A, INF=10**9+1):
    st, st_idx, offset = segtree_init(N)
    l = 0
    for a in A[::-1]:
        k, v = segtree_find_le(st, st_idx, offset, -a-1)  
        if k == -1:
            segtree_update(st, st_idx, offset, l, -a)
            l += 1
        else:
            segtree_update(st, st_idx, offset, k, -a)
    return l


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right


def read():
    N = int(input().strip())
    A = [int(input().strip()) for _ in range(N)]
    return N, A


def solve(N, A, INF=10**9+1):
    # LIS
    
    dp = [INF for i in range(N)]
    for i in range(N):
        a = A[N-i-1]
        idx = bisect_right(dp, a)
        dp[idx] = a
    return bisect_right(dp, INF-1)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Verdicts: Runtime Error

Accepted