Problem:
Longest Increasing Subsequence For a given sequence A = {a 0 , a 1 , ... , a n-1 } , find the length of the longest increasing subsequnece (LIS) in A . An increasing subsequence of A is defined by a subsequence {a i 0 , a i 1 , ... , a i k } where 0 ≤ i 0 < i 1 < ... < i k < n and a i 0 < a i 1 < ... < a i k . Input  n  a 0  a 1 : a n-1   In the first line, an integer n is given. In the next n lines, elements of A are given. Output The length of the longest increasing subsequence of A . Constraints  1 ≤ n ≤ 100000  0 ≤ a i ≤ 10 9  Sample Input 1 5
5
1
3
2
4 Sample Output 1 3 Sample Input 2 3
1
1
1 Sample Output 2 1

Solution (Python):
from bisect import bisect_left as bl
INF = 10 ** 10
n = int(input())
alst = [int(input()) for _ in range(n)]
dp = [INF] * (n + 1)
dp[0] = -1
ans = 0
for a in alst:
  ind = bl(dp, a)
  dp[ind] = a
  ans = max(ans, ind)
print(ans)

Solution (Python):
from bisect import bisect_left

INF = 10**9 + 1
n = int(input())
dp = [INF] * (n+1)

for _ in range(n):
    a = int(input())
    i = bisect_left(dp, a)
    dp[i] = a
    
print(bisect_left(dp, INF))

Solution (Python):
import bisect


n = int(input())
A = [int(input()) for _ in range(n)]

def LIS2(A):
    n = len(A)
    INF = max(A)+10
    L = [INF]*n
    length = 0

    for i in range(n):
        ins_ind = bisect.bisect_left(L,A[i])
        if length == ins_ind:
            length += 1
        L[ins_ind] = A[i]
    
    return length,L

L , _ = LIS2(A)
print(L)

Solution (Python):
from bisect import bisect_left

N = int(input())

A = [int(input()) for _ in range(N)]

LIS = [A[0]]                            

for a in A[1:]:
    if a > LIS[-1]:                     
                                        
        LIS.append(a)
    else:
        LIS[bisect_left(LIS, a)] = a    

print(len(LIS))

Solution (Python):
from bisect import *
INF=10**18
n=int(input())
a=[int(input()) for i in range(n)]

dp=[INF]*(n+1)
dp[0]=-1
for i in range(n):
    b=bisect_left(dp,a[i])
    dp[b]=a[i]
ans=-1
for i in range(n+1):
    if dp[i]==INF:
        break
    ans=i
print(ans)

Solution (Python):

import bisect

N = int(input())
seq = [0] * N
for i in range(N):
  seq[i] = int(input())

LIS = [seq[0]]

for i in range(len(seq)):
    if seq[i] > LIS[-1]:
        LIS.append(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
    

print(len(LIS))

Solution (Python):
import sys
import bisect

input = sys.stdin.readline


def main():
    N = int(input())
    C = [int(input()) for _ in range(N)]

    x = []
    for c in C:
        if x:
            if x[-1] < c:
                x.append(c)
            else:
                y = bisect.bisect_left(x, c)
                x[y] = c
        else:
            x.append(c)

    print(len(x))

if __name__ == '__main__':
    main()

Solution (Python):
import bisect
n= int(input())
a=[]
for _ in range(n):
    a.append(int(input()))

inf= 10**9
min_lis= [a[0]]
for i in range(1,n):
    if a[i]> min_lis[-1]:
        min_lis.append(a[i])
    else:
        min_lis[bisect.bisect_left(min_lis,a[i])]=a[i]
print(len(min_lis))
    
'''
if a==[3,1000000000,999999998,999999999]:
    res=2
print(res)
'''

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left
INF = 1 << 40

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    dp = [INF] * (N + 1)
    dp[0] = -1
    for a in A:
        idx = bisect_left(dp,a)
        dp[idx] = a
    ans = 1
    for i in range(N,-1,-1):
        if dp[i] < INF:
            ans = i
            break
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    import bisect
    N=int(input())
    lists=[int(input()) for _ in range(N)]
    inf = 10**15
    dp=[inf  for i in range(N+1)]
    for i in range(N):
        index=bisect.bisect_left(dp,lists[i])
        dp[index]=lists[i]
    for i in range(N+1):
        if dp[i]==inf:
            print(i)
            break
if __name__=="__main__":
    solve()

Solution (Python):
import bisect

INF = 10 ** 9 + 1

N = int(input())
S = [int(input()) for l in range(N)]
L = [S[0]]

for i in range(1, N):
    if L[-1] < S[i]:
        L.append(S[i])
    else:
        L[bisect.bisect_left(L, S[i])] = S[i]

print(len(L))

Solution (Python):
import bisect

n=int(input())
seq=[int(input()) for _ in range(n)]

dp=[seq[0]]
for num in seq:
    if num > dp[-1]:
        dp.append(num)
    else:
        dp[bisect.bisect_left(dp,num)] = num

print(len(dp))

Solution (Python):

from bisect import bisect_left
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,*A = map(int, read().split())

    LIS = [A[0]]
    for a in A:
        if a > LIS[-1]:
            LIS.append(a)
        else:
            LIS[bisect_left(LIS, a)] = a

    ans = len(LIS)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def lis(a):
    dp = [INF]*len(a)
    for i in a:
        idx = bisect.bisect_left(dp, i)
        dp[idx] = i
    return bisect.bisect_left(dp, INF)

def resolve():
    n = I()
    a = [I() for _ in range(n)]

    print(lis(a))

if __name__ == '__main__':
    resolve()

Solution (Python):
from bisect import bisect_left

INF = 10**9 + 1
n = int(input())
dp = [INF] * (n+1)

for _ in range(n):
    a = int(input())
    i = bisect_left(dp, a)
    dp[i] = a
    

print(bisect_left(dp, INF))

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7
INF = 1 << 60




from bisect import bisect_left

def resolve():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    dp = [INF]*(N+1)
    for i in range(N):
        ind = bisect_left(dp, A[i])
        dp[ind] = A[i]

    ans = bisect_left(dp, INF)
    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):

import bisect

INF = float('inf')

n = int(input())
A = []
for _ in range(n):
    a = int(input())
    A.append(a)

dp = [INF for _ in range(n)]

for a in A:
    update_index = bisect.bisect_left(dp, a)
    dp[update_index] = a

print(bisect.bisect_left(dp, INF))

Solution (Python):
import bisect

INF = 10 ** 10


N = int(input())
dp = [INF] * (N + 1)
dp[0] = -1

ans = 0
for i in range(N):
    a = int(input())
    j = bisect.bisect_left(dp, a)
    dp[j]=a
    ans = max(j,ans)
print(ans)

Solution (Python):
import bisect

N = int(input())
Ali = [int(input()) for _ in range(N)]
dp = [10**10]*N
dp[0] = Ali[0]

for i in range(1,N):
  a = Ali[i]
  if a > dp[i-1]:
    dp[i] = a
  else:
    dp[bisect.bisect_left(dp, a)] = a
    
print(bisect.bisect_left(dp, 10**10))

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
def solve(N,A):
    lis = []
    for i in range(N):
        ind = bisect_left(lis,A[i])
        if ind == len(lis):
            lis.append(A[i])
        else:
            lis[ind] = A[i]
    ans = len(lis)
    return ans
print(solve(N,A))

Solution (Python):
import bisect
n = int(input())
l = []
for _ in range(n):
    l.append(int(input()))

dp = [float('inf')]*n

for num in l:
    i = bisect.bisect_left(dp,num)
    
    dp[i] = num

for j in range(n):
    if dp[j] == float('inf'):
        print(j)
        exit()
print(n)

Solution (Python):






INF = float("inf")
import sys,bisect
sys.setrecursionlimit(15000)

n = int(sys.stdin.readline())
a = [int(sys.stdin.readline()) for _ in range(n)]










import bisect
dp = [float("inf")]*n
dp[0] = a[0]
l = 0
for i in range(1,n):
  if dp[l] < a[i]:
    l += 1
    dp[l] = a[i]
  else:
    j = bisect.bisect_left(dp,a[i])
    dp[j] = a[i]
print(bisect.bisect_left(dp,float("inf")))

Solution (Python):



import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*a = map(int,read().split())


from bisect import bisect_left
INF = 2*10**9
dp = [INF]*n
for ai in a:
    dp[bisect_left(dp,ai)] = ai
ans = bisect_left(dp,INF)
print(ans)

Solution (Python):
from bisect import bisect_left
N = int(input())
A = [int(input()) for _ in range(N)]


INF = 10 ** 10
dp = [INF] * N
res = 0
for i in range(N):
    idx = bisect_left(dp,A[i])
    dp[idx] = A[i]
print(bisect_left(dp, INF))

Solution (Python):
from bisect import bisect_right

def LIS(A):
    B = [INF for _ in range(len(A))]
    B[0] = A[0]
    for i in range(1,len(A)):
        pt = bisect_right(B,A[i])
        if B[pt-1] != A[i]:
            B[pt] = A[i]
    return bisect_right(B,INF-1)

n = int(input())
A = [int(input()) for _ in range(n)]
INF = 10**9+2

print(LIS(A))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect 
from collections import defaultdict 


class Segtree: 
    def __init__(self, n, A, segfunc, ide_ele):
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n-1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = A[i]
        for i in range(self.num-1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])
        
    def update(self, ind, val): 
        ind += self.num
        self.tree[ind] = val
        while ind > 1:
            self.tree[ind >> 1] = self.segfunc(self.tree[ind], self.tree[ind^1])
            ind >>= 1

    def find(self, l, r): 
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

N = ii()
A = [ii() for i in range(N)]
compress = lambda arr: list(map({e: i for i, e in enumerate(sorted(set(arr)))}.__getitem__, arr))
A = compress(A)
'''

d = defaultdict(int)
for i, num in enumerate(sorted(list(set(A)))):
    d[num] = i
for i, num in enumerate(A):
    A[i] = d[num]
'''

dp = [0 for _ in range(N)]
seg = Segtree(N, dp, max, 0)

for num in A:
    dp[num] = seg.find(0, num) + 1
    seg.update(num, dp[num])

print(max(dp))

Solution (Python):
from bisect import bisect_left
n=int(input())
A=[int(input()) for _ in range(n)]

DP=[A[0]]
for i in range(1,n):
    num=A[i]
    if DP[-1]<num:
        DP.append(num)
    else:
        index=bisect_left(DP,num)
        DP[index]=num
print(len(DP))

Solution (Python):
from bisect import bisect_left

n = int(input())
A = [int(input()) for _ in range(n)]


def LIS(arr):
	dp = [arr[0]]
	for i in arr[1:]:
		if dp[-1] < i:
			dp.append(i)
		else:
			dp[bisect_left(dp, i)] = i
	return len(dp)

print(LIS(A))

Solution (Python):
import bisect
n=int(input())
l=[float('inf')]*n
for i in range(n):
    a=int(input())
    p=bisect.bisect_left(l,a)
    l[p]=a
p=0
while p<n and l[p]!=float('inf'):
    p+=1
print(p)

Solution (Python):
from bisect import bisect_left
N = int(input())
As = [int(input()) for _ in range(N)]

INF = 10**20
dp = [As[0]]

for i in range(1, N):
    a = As[i]
    if a>dp[-1]:
        dp.append(a)
    else:
        dp[bisect_left(dp, a)] = a
print(len(dp))

Solution (Python):
import bisect

N = int(raw_input())

LIS = []

for i in range(N):
    a = int(raw_input())
    z = bisect.bisect_left(LIS, a)
    if z >= len(LIS):
        LIS.append(a)
    else:
        LIS[z] = a

print len(LIS)

Solution (Python):
import bisect
n = int(input())
A = [int(input()) for i in range(n)]


L = [A[0]]
for i in range(n):
    if A[i] > L[-1]:
        L.append(A[i])
    else:
        j = bisect.bisect_left(L, A[i])
        L[j] = A[i]
print(len(L))

Solution (Python):
import bisect
N = int(input())
seq = [int(input()) for _ in range(N)]

LIS = [seq[0]]
for i in range(len(seq)):
    if seq[i] > LIS[-1]:
        LIS.append(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]

print(len(LIS))

Solution (Python):
def LIS(seq: list) -> int:
    from bisect import bisect_left

    L = [seq[0]]
    for i in range(len(seq)):
        if seq[i] > L[-1]:
            L.append(seq[i])
        else:
            idx = bisect_left(L, seq[i])
            L[idx] = seq[i]
    return len(L)


N = int(input())
A = [int(input()) for _ in range(N)]
print(LIS(A))

Solution (Python):
n=int(input())
l=[]
from bisect import bisect_left
for i in range(n):
    a=int(input())
    if l==[]:
        l.append(a)
    else:
        if l[-1]<a:
            l.append(a)
        else:
            l[bisect_left(l,a)]=a

print(len(l))

Solution (Python):
n=int(input())
a=[int(input()) for _ in range(n)]
inf=10**10
l=[inf]*n
import bisect
for i in range(n):
	r=bisect.bisect_left(l,a[i])
	l[r]=a[i]
cnt=0
for i in range(n):
	if l[i]!=inf:
		cnt+=1
	else:
		break
print(cnt)

Solution (Python):
n = int(input())
A = [int(input()) for _ in range(n)]
INF = 10**18

dp = [INF]*(n+1)

dp[0] = -1

import bisect

for i in range(n):
    r_idx = bisect.bisect_right(dp, A[i])
    
    if dp[r_idx-1]<A[i] and dp[r_idx]>A[i]:
        dp[r_idx] = A[i]
        
ans = -1
dp.append(INF)
for i in range(n+2):
    if dp[i]==INF:
        ans = i-1 
        break

print(ans)

Solution (Python):
from bisect import bisect_left
n = int(input())
a = [int(input()) for _ in range(n)]

INF = 10**9
dp = [INF for _ in range(n)]
dp[0] = a[0]

for i in range(1, n):
    idx = bisect_left(dp, a[i])
    dp[idx] = a[i]

print(len(list(filter(lambda x: x != INF, dp))))

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = IR(n)
    dp = [float("inf")]*n
    for i in a:
        j = bisect.bisect_left(dp,i)
        dp[j] = i
    print(n-dp.count(float("inf")))
    return


if __name__ == "__main__":
    solve()

Solution (Python):
from bisect import bisect_left

n = int(input())
a = [int(input()) for i in range(n)]

dp = [float("inf")] * n


for i in range(n):
    dp[bisect_left(dp, a[i])] = a[i]

print(bisect_left(dp, float("inf")))

Solution (Python):
from math import inf
import bisect

n = int(input())
A = [int(input()) for _ in range(n)]
dp = [inf] * n
for a in A:
    j = bisect.bisect_left(dp, a)
    dp[j] = a
ans = 0
for i in range(n):
    if dp[i] != inf:
        ans = i
print(ans + 1)

Solution (Python):
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op 
        self.e = e 
        self.v = self._build(lst)
        
    def _build(self, lst):
        
        
        tree = [self.e] * (self.N - 1) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 2, -1, -1):
            tree[i] = self.op(tree[2*i + 1], tree[2*i + 2])
        return tree
    
    def __getitem__(self, i):
        return self.v[i + self.N - 1]
    
    
    def update(self, i, x):
        i += self.N - 1
        self.v[i] = x
        while i > 0:
            i -= 1; i >>= 1
            self.v[i] = self.op(self.v[2*i + 1], self.v[2*i + 2])
    
    
    def query(self, l, r):
        left = l + self.N - 1
        right = r + self.N - 1
        L = self.e; R = self.e
        while left < right:
            if left & 1 == 0: 
                L = self.op(L, self.v[left])
                left += 1
            if right & 1 == 0: 
                right -= 1
                R = self.op(self.v[right], R)
            left -= 1; left >>= 1
            right >>= 1
        return self.op(L, R)

def coord_compress(A):
    B = {a: i for i, a in enumerate(sorted(set(A)))}
    return [B[a] for a in A]
    
def LIS(A):
    A = coord_compress(A)
    dp = SegmentTree([0] * len(A), max, 0)
    for a in A:
        dp.update(a, max(dp[a], dp.query(0, a) + 1))
    return max(dp)

N = int(input())
A = [int(input()) for _ in range(N)]
print(LIS(A))

Solution (Python):
from bisect import bisect_left


def solve(n, sx):
    
    tbl = [float('inf')]*n
    

    for i in range(n):
        idx = bisect_left(tbl, sx[i])
        tbl[idx] = sx[i]
        
        
        
        
        
        

    return bisect_left(tbl, float('inf'))


if __name__ == '__main__':
    n = int(input())
    sx = []
    for _ in range(n):
        sx.append(int(input()))

    print(solve(n, sx))

Solution (Python):
from bisect import bisect_left, bisect_right, insort_left
from collections import deque


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = deque(sorted(ls))  

    def __repr__(self):
        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):
        idx=self.bisect_left(x)
        self.bst.insert(idx ,x)

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

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

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) + 1
        if idx_del - 1 == len(self.bst):  
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]



N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))


L = BinarySearchTree()
L.insert(A[0])
length = 0
for a in A[1:]:
    L.insert_replace_right(a)
    
    
    
    


print(len(L))

Solution (Python):
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]

li = [a[0]]
for i in a[1:]:
    if i > li[-1]:
        li.append(i)
    else:
        li[bisect.bisect_left(li,i)] = i
print (len(li))

Solution (Python):

from typing import Sequence


def longest_subsequence(A: Sequence[int], is_equal: bool, is_increasing: bool) -> int:
    """
    Compute the length of LIS or LDS.

    Args:
        A (Sequence[int]): a list or tuple to compute.
        is_equal (bool): permit adjacent numbers in subsequence to equal.
        is_increasing (bool): compute an increasing subsequence or decreasing one.
    Returns: (int) the length of a subsequence.
    """
    from bisect import bisect_left, bisect_right

    bs = bisect_right if is_equal else bisect_left
    compare = (lambda x, y: x >= y) if is_equal else (lambda x, y: x > y)
    if not is_increasing:
        A = A[::-1]

    dp = [A[0]]  
    for i in A[1:]:
        if compare(i, dp[-1]):
            dp.append(i)
        else:
            dp[bs(dp, i)] = i
    return len(dp)


def main():
    N, *A = map(int, open(0))
    ans = longest_subsequence(A, is_equal=False, is_increasing=True)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def lis(N, A):
    from bisect import bisect_left

    
    dp = [-1]  
    for a in A:
        if dp[-1] < a:
            dp.append(a)
        else:
            
            idx = bisect_left(dp, a)
            dp[idx] = a
    print(len(dp) - 1)

N = int(input())
A = [int(input()) for _ in range(N)]
lis(N, A)

Solution (Python):
import bisect

n = int(input())
A = [int(input()) for _ in range(n)]

que = [A[0]]

for a in A[1:]:
    if a > que[-1]:
        que.append(a)
    else:
        idx = bisect.bisect_left(que, a)
        que[idx] = a

print(len(que))

Solution (Python):
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
LIS = [a[0]]
for i in range(n):
    if a[i] > LIS[-1]:
        LIS.append(a[i])
    else:
        LIS[bisect.bisect_left(LIS,a[i])] = a[i]
print(len(LIS))

Solution (Python):
from bisect import bisect_left

def LIS(arr):
    n = len(arr)
    lis = [arr[0]]
    for a in arr:
        if a > lis[-1]:
            lis.append(a)
        else:
            lis[bisect_left(lis,a)] = a
    return len(lis)

import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

print(LIS(A))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline()[:-1]
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def MF(): return map(float, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LF(): return list(map(float, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def main():
    n=II()
    lis=[]
    for _ in range(n):
        a=II()
        i=bisect_left(lis,a)
        if i==len(lis):lis.append(a)
        else:lis[i]=a
    print(len(lis))

main()

Solution (Python):

"""
aaa
"""

import sys
import bisect




def main():
    length = int(input())
    X = [0] * length
    for i, line in enumerate(sys.stdin): 
        X[i] = int(line)
    print(LIS2(X))

def LIS(X):
    res = 0
    N = len(X)
    dp = [1] * N
    for i in range(N):
        for j in range(i):
            if i == 0: dp[0] = 1
            elif X[i] > X[j]: dp[i] = max(dp[i], dp[j]+1)
        res = max(res, dp[i])
    return res

def LIS2(X):
    INF = 10 ** 10
    N = len(X)
    dp = [INF] * (N+1)
    dp[0] = -1
    for a in X:
        idx = bisect.bisect_right(dp, a-1)
        dp[idx] = min(a, dp[idx])
    return max(i for i in range(N+1) if dp[i] < INF)

    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from bisect import bisect_left

def main():
    n = int(input().strip())
    a = [0] * n
    for i in range(n):
        a[i] = int(input().strip())
    l = [a[0]]
    for i in range(1, n):
        if a[i] <= l[-1]:
            k = bisect_left(l, a[i])
            l[k] = a[i]
        else:
            l.append(a[i])
    print(len(l))

if __name__ == '__main__':
    main()

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    A = [int(input()) for i in range(N)]

    Inf = 10**9 + 1
    dp = [Inf] * N

    from bisect import bisect_left
    n = 0

    for a in A:
        i = bisect_left(dp, a, 0, n)

        if a < dp[i]:
            dp[i] = a
            n = max(n, i+1)
    print(n)

if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
import bisect

def input():
    return sys.stdin.readline()
def lis(n, A):
    L = [0 for i in range(n + 1)]
    L[0] = A[0]
    length = 1
    for i in range(1, n):
        if L[length - 1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            index = bisect.bisect_left(L, A[i], 0, length)
            L[index] = A[i]
    return length
if __name__=="__main__":
    n = int(input())
    A = [int(input()) for _ in range(n)]
    print(lis(n,A))

Solution (Python):
from bisect import bisect_left

dp = [-1]
n = int(input())
a = (int(input()) for _ in range(n))
for ai in a:
    if dp[-1] < ai:
        dp.append(ai)
    else:
        dp[bisect_left(dp, ai)] = ai
        
print(len(dp) - 1)

Solution (Python):

import bisect


def lis():
    L.append(A[0])
    length = 1
    
    for i in range(1, n):
        if L[length-1] < A[i]:
            L.append(A[i])
            length += 1
        else:
            if L[bisect.bisect_left(L, A[i])] >= A[i]:
                L[bisect.bisect_left(L, A[i])] = A[i]
            else:
                L[bisect.bisect_right(L, A[i])] = A[i]
    return length


n = int(input())
A = []
L = []
for i in range(n):
    A.append(int(input()))

print(lis())

Solution (Python):
def binary_search(sorted_list, a):
    left = 0
    right = len(sorted_list)
    while left < right:
        mid = (left + right) // 2
        if sorted_list[mid] < a:
            left = mid + 1
        else:
            right = mid
    return left


def lis(A):
    sorted_list = [10000000000]
    for a in A:
        if sorted_list[-1] < a:
            sorted_list.append(a)
        else:
            sorted_list[binary_search(sorted_list, a)] = a
    return len(sorted_list)
        

if __name__ == "__main__":
    n = int(input())
    a = [int(input()) for i in range(n)]

    print(lis(a))

Solution (Python):



import bisect

N = int(input())
Data = []
for _ in range(N):
    Data.append(int(input()))

LIS = []
LIS.append( Data[0] )

for i in range(1,N):
    n = Data[i]
    if n > LIS[-1]:
        LIS.append(n)
    else:
        p = bisect.bisect_left(LIS,n)
        LIS[p] = n

print(len(LIS))

Solution (Python):

import sys, math,bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0

n=int(input())
A=[int(input()) for i in range(n)]
dp=[inf]*(n+10)
dp[0]=A[0]
length=1
for i in range(1,n):
    if dp[length-1]<A[i]:
        dp[length]=A[i]
        length+=1
    else:
        
        dp[bisect.bisect_left(dp,A[i])]=A[i]
print(length)

Solution (Python):
from bisect import bisect_left


def main():
    n = int(input())
    a = [-1] * n
    for i in range(n):
        a[i] = int(input())

    ans = solve3(n, a)
    
    print(ans)


def solve1(n, a):
    INF = 10 ** 9
    dp = [INF for i in range(n + 1)]
    for i in range(n):
        for j in range(1, i + 2):
            if j == 1 or a[i] > dp[j - 1]:
                dp[j] = min(dp[j], a[i])

    ret = 0
    for i in range(n + 1):
        if dp[i] < INF:
            ret = i
    return ret


def solve2(n, a):
    INF = 10 ** 9
    dp = [INF for i in range(n)]
    for i in range(n):
        for j in range(i + 2):
            if j == 0 or a[i] > dp[j - 1]:
                dp[j] = min(dp[j], a[i])
    ans = 0
    for i in range(n):
        if dp[i] < INF:
            ans = i + 1
    return ans


def solve3(n, a):
    INF = 10 ** 9
    dp = [INF for i in range(n)]
    for i in range(n):
        ix = bisect_left(dp, a[i])
        dp[ix] = a[i]
    ans = bisect_left(dp, INF)
    return ans


def solve4(n, a):
    INF = 10 ** 10
    dp = [INF for i in range(n)]
    for elt in a:
        ix = bisect_left(dp, elt)
        dp[ix] = elt

    ans = 0
    for i in range(n):
        if dp[i] < INF:
            ans = i + 1

    return ans


main()

Solution (Python):
import bisect


n = int(input())
a = [0] * n
for i in range(n):
    a[i] = int(input())
L = []
L.append(a[0])
for i in range(1,n):
    p = bisect.bisect_right(L, a[i])
    if L[-1] == a[i]:
        continue;
    elif p == len(L):
        L.append(a[i])
    else:
        if L[p-1] != a[i]:
            L[p] = a[i]
print(len(L))

Solution (Python):
import bisect

def main():
    A = []
    length = 0
    
    for i in range(int(input())):
        a = int(input())
    
        idx = bisect.bisect_left(A, a)
        
        if idx == length:
            A.append(a)
            length += 1
            
        else: A[idx] = a
        
    print(length)
            
if __name__ == '__main__':
    main()

Solution (Python):
import bisect

N = int(input())
A = [10**9 + 1]

for i in range(N):
  target = int(input())
  target_idx = bisect.bisect_left(A, target)
  if target_idx > len(A) - 1:
    A.append(target)
  else:
    A[target_idx] = target

print(len(A))

Solution (Python):
from bisect import bisect_left as bl
N,*A=map(int,open(0))
r=[A[0]]+[1e9]*N
for a in A[1:]:i=bl(r,a);r[i]=min(r[i],a)
print(bl(r,1e9))

Solution (Python):
from sys import stdin

def interval(l, e):
    left = 0
    right = len(l)
    while left < right:
        mid = (left + right) // 2
        if l[mid] < e:
            left = mid + 1
        else:
            right = mid
    return left

def LIS(n, a):
    l = [a[0]]
    for e in a[1:]:
        if l[-1] < e:
            l.append(e)
        else:
            l[interval(l, e)] = e
    return len(l)


def main():
    n = int(input())
    a = list(map(int, stdin.readlines()))
    print(LIS(n, a))


main()

Solution (Python):
from bisect import bisect
import sys


if __name__ == "__main__":
    n = int(input())
    a = [0] * n
    for i in range(n):
        a[i] = int(input())

    dp = [sys.maxsize] * (n + 1)
    dp[0] = -1

    for elem in a:
        idx = bisect(dp, elem - 1)
        dp[idx] = min(elem, dp[idx])

    ans = max(i for i in range(n + 1) if dp[i] < sys.maxsize)
    print(ans)

Solution (Python):
import bisect
N = int(input())
C = [int(input())for _ in range(N)]
INF = float('inf')
dp = [INF]*N
max_ind = 0
for c in C:
    index = bisect.bisect_left(dp,c)
    dp[index] = c
    max_ind = max(max_ind,index)

print(max_ind+1)

Solution (Python):
import bisect
n = int(input())
L = []
for i in range(n):
    L.append(int(input()))
dp = [float('inf')]*n
for i in range(n):
    k = bisect.bisect_left(dp,L[i])
    dp[k] = L[i]
ans = 0
for i in range(n):
    if dp[i] != float('inf'):
        ans += 1
    else:
        break
print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
INF = 10**10
memory = [INF for _ in range(N)]
ans = 0
def search(x):
  l = 0
  r = len(memory) - 1
  cp = (l + r) // 2
  while r - l >= 0:
    cp = (l + r) // 2
    if memory[cp] >= x:
      r = cp - 1
    else:
      l = cp + 1
  return l
ans = 0 
for a in A:
  point = search(a)
  memory[point] = a
  ans = max(ans, point)

print(ans + 1)

Solution (Python):
import  bisect
n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))

Ans=[-1]

for i in range(n):
    
    
        
    
    
    
                
    
    
    l=bisect.bisect_left(Ans,a[i])
    if l==len(Ans):
        Ans.append(a[i])
    else:
        Ans[l]=a[i]



print(len(Ans)-1)