Problem:


Score : 500 points

Problem Statement

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.

Constraints

1 \leq N \leq 10^5

0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the minimum number of colors required to satisfy the condition.

Sample Input 1

5
2
1
4
5
3

Sample Output 1

2

We can satisfy the condition with two colors by, for example, painting 2 and 3 red and painting 1, 4, and 5 blue.

Sample Input 2

4
0
0
0
0

Sample Output 2

4

We have to paint all the integers with distinct colors.



Sample input:
5
2
1
4
5
3


Sample output:
2

Submission status: Accepted

Solution code:
from random import random


class TreapNode():
    """Treapが保持するノードを定義する。
    ノードは値と優先度、および親と子へのポインタを持つ。"""
    def __init__(self, val):
        self.val = val
        self.priority = random()
        self.parent, self.right, self.left = None, None, None

class Treap():
    def __init__(self, multiset=True):
        self.root = None

    def search(self, val: int) -> bool:
        """集合に値valを持つノードが存在するかどうかを返す。"""
        ptr = self.root
        while ptr is not None:
            if ptr.val == val:
                return True
            if val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
        return False

    def insert(self, val: int) -> bool:
        """集合に値valを持つノードを挿入する。
        挿入に成功したときTrue、失敗したときにFalseを返す。"""
        if self.root is None:
            self.root = TreapNode(val)
            return True

        # ノードの挿入
        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    ptr.left = TreapNode(val)
                    ptr.left.parent = ptr
                    ptr = ptr.left
                    break
                ptr = ptr.left
            else:
                if ptr.right is None:
                    ptr.right = TreapNode(val)
                    ptr.right.parent = ptr
                    ptr = ptr.right
                    break
                ptr = ptr.right

        # 木の回転によりヒープ性を保つ
        while (ptr.parent is not None) and (ptr.parent.priority > ptr.priority):
            if ptr.parent.right == ptr:
                self.rotate_left(ptr.parent)
            else:
                self.rotate_right(ptr.parent)
        if ptr.parent is None:
            self.root = ptr 
        return True

    def delete(self, val: int) -> True:
        """集合から値valを持つノードを削除する。
        削除に成功したときTrue、失敗したときにFalseを返す。"""
        if self.root is None:
            return False

        ptr = self.root         
        while True: 
            if ptr is None:
                return False
            if ptr.val == val:
                break
            elif val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right

        # 木の回転により削除したいノードを葉に持っていく
        while (ptr.left is not None) or (ptr.right is not None):
            if ptr.left is None:
                self.rotate_left(ptr)
            elif ptr.right is None:
                self.rotate_right(ptr)
            elif ptr.left.priority < ptr.right.priority:
                self.rotate_right(ptr)
            else:
                self.rotate_left(ptr)
            if self.root == ptr:
                self.root = ptr.parent

        # ノードの削除
        if ptr.left is None and ptr.right is None:
            if ptr == self.root:
                self.root = None
            elif ptr.parent.left == ptr:
                ptr.parent.left = None
            else:
                ptr.parent.right = None      
        return True

    def rotate_left(self, ptr):
        """木の左回転を行う"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def rotate_right(self, ptr):
        """木の右回転を行う"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def search_less_than(self, val):
        if val == None:
            return None
        ptr = self.root
        ret = None
        while ptr is not None:
            if ptr.val >= val:
                ptr = ptr.left
            else:
                ret = ptr.val
                ptr = ptr.right
        return ret

n = int(input())
a = [int(input()) for i in range(n)]
tp = Treap()
cnt = 0
for i in range(n):
    num = tp.search_less_than(a[i])
    if num is None:
        tp.insert(a[i])
        cnt += 1
    else:
        tp.delete(num)
        tp.insert(a[i])
print(cnt)

Submission status: Accepted

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

B = []
import bisect
for i, a in enumerate(A):
    if len(B) == 0:
        B.append(-a)
    else:
        j = bisect.bisect_right(B, -a)
        #print(j)
        if j == len(B):
            B.append(-a)
        elif j == 0:
            B[0] = -a
        else:
            B[j] = -a
    #print(B)
#print(B)
print(len(B))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
from bisect import bisect

arr = []
for a in A:
    i = bisect(arr, -a)
    if i==len(arr):
        arr.append(-a)
    else:
        arr[i] = -a
print(len(arr))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.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_right(dp,-i)
        dp[j] = -i
    print(n-dp.count(float("inf")))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def binary_search(c1, c2):
    m = (c1 + c2 + 1) // 2
    if abs(c1 - c2) <= 1:
        return m
    else:
        if dp[m] < a:
            c1 = m
        else:
            c2 = m
        return binary_search(c1, c2)

n = int(input())
dp = [-1 for _ in range(n)]
for _ in range(n):
    a = int(input())
    m = binary_search(n - 1, -1)
    dp[m] = a
ans = 0
for i in dp:
    if i == -1:
        break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
n = int(input())
a = int(input())
x = [a * (-1)]
for _ in range(n-1):
  a = int(input()) * (-1)
  if a >= x[-1]:
    x.append(a)
  else:
    index = bisect_right(x, a)
    x[index] = a
print(len(x))

Submission status: Accepted

Solution code:
#E
from collections import deque
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
result = deque()

for i in a:
    idx = bisect.bisect_left(result,i)
    if idx == 0:
        result.appendleft(i)
        
    else:
        result[idx-1] = i
        
print(len(result))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right as bi_r, bisect_left as bi_l
inf = float('inf')

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

def main():
  res = [inf] * n
  for x in a[::-1]:
    res[bi_r(res, x)] = x
  print(bi_l(res, inf))

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def resolve():
    import bisect
    n = int(input())
    a = [int(input()) for _ in range(n)]
    m = []
    for i in range(n-1, -1, -1):
        if i == n-1:
            m.append(a[i])
        else:
            if m[-1] <= a[i]:
                m.append(a[i])
            else:
                j = bisect.bisect_right(m, a[i])
                m[j] = a[i]
    print(len(m))

resolve()

Submission status: Accepted

Solution code:
def resolve():
    import bisect
    n = int(input())
    a = [int(input()) for _ in range(n)]
    m = []
    for i in range(n-1, -1, -1):
        if i == n-1:
            m.append(a[i])
        else:
            if m[-1] <= a[i]:
                m.append(a[i])
            elif m[0] > a[i]:
                m[0] = a[i]
            else:
                j = bisect.bisect_right(m, a[i])
                m[j] = a[i]
    print(len(m))
resolve()

Submission status: Accepted

Solution code:
#ABC134-E Sequence Decomposing
"""
与えられたリストを反転した場合の広義(重複を許した)LIS(最長増加部分列)
の長さが答え。
"""
import bisect
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0


lst1 = []
n = int(readline())
for i in range(n):
    lst1.append(int(readline()))

lst1.reverse() #減少→増加へ

def LIS(lst):
    dp=[]
    for i in lst:
        pos=bisect.bisect_right(dp,i) #rightなら広義、leftなら狭義
        if len(dp)<=pos:
            dp.append(i)
        else:
            dp[pos]=i
    return len(dp)

print(LIS(lst1))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

n = int(input())
max_color = deque([int(input())])
for _ in range(n-1):
  a = int(input())
  if a <= max_color[0]:
    max_color.appendleft(a)
  else:
    index = bisect_left(max_color, a) - 1
    max_color[index] = a
print(len(max_color))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# 二分木
import bisect

n = int(input())
a = []

for _ in range(n):
    ai = int(input()) * -1
    i = bisect.bisect_right(a,ai)
    if(i==len(a)):
        a.append(ai)
    else:
        a[i] = ai

print(len(a))

Submission status: Accepted

Solution code:
import sys
import bisect

def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [int(readline()) for _ in range(n)]
    res = []
    for i in range(n-1, -1, -1):
        p = bisect.bisect_right(res, a[i])
        if len(res) == p:
            res.append(a[i])
        else:
            res[p] = a[i]
    print(len(res))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[-1]*(N)
for a in A:
    i=bisect.bisect_left(color,a)
    color[i-1]=a
print(N-bisect.bisect_right(color,-1))

Submission status: Accepted

Solution code:
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[]
A=A[::-1]
for a in A:
    i=bisect.bisect_right(color,a)
    if i==len(color):
        color.append(a)
    else:
        color[i]=a
print(len(color))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

N = int(input())

color = []
color.append(int(input()))

for i in range(N-1):
  A = int(input())
  
  if color[-1] >= A:
    color.append(A)

  else:
    color.reverse()
    l = bisect_left(color,A)
    color[l-1] = A
    color.reverse()


print(len(color))

Submission status: Accepted

Solution code:
N = int(input())
A = [-1*int(input()) for _ in range(N)]


def LIS(seq: list) -> int:
    """param: seq
    return:LISの長さ（a_i =< a_j）
    """
    from bisect import bisect_right
    N = len(seq)
    L = [seq[0]]
    for i in range(1, N):
        if seq[i] > L[-1]:
            L.append(seq[i])
        else:
            idx = bisect_right(L, seq[i])
            if idx == len(L):
                L.append(None)  # avoid Out-of-Index-Error
            L[idx] = seq[i]
    return len(L)


print(LIS(A))

Submission status: Accepted

Solution code:


from bisect import *



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

    B =[A[0]]

    A=A[1:]
    for  i in A:
        if i >= B[-1]:
            B.append(i)
            continue
        point = bisect_right(B,i)
        B[point]=i

    print(len(B))
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
# 狭義単調増加部分列
import bisect
from collections import deque

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

for i in range(n):
    if len(que) == 0:
        deque.appendleft(que, A[i])
    else:
        idx = bisect.bisect_left(que, A[i])
        if idx == 0:
            deque.appendleft(que, A[i])
        else:
            que[idx - 1] = A[i]

ans = len(que)
print(ans)

Submission status: Accepted

Solution code:
import bisect

f_inf = float("inf")
n = int(input())
A = [int(input()) for _ in range(n)][::-1]
dp = [f_inf for _ in range(n + 1)]

for a in A:
    idx = bisect.bisect_right(dp, a)
    dp[idx] = a

ans = bisect.bisect_left(dp, f_inf)
print(ans)

Submission status: Accepted

Solution code:
def main():
    from heapq import heappop, heappush
    import sys

    input = sys.stdin.readline

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

    def binary_search(b, x):
        ok, ng = len(b), -1
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if b[mid] < x:
                ok = mid
            else:
                ng = mid
        return ok

    b = [-1]
    for x in a:
        i = binary_search(b, x)
        if i == len(b):
            b.append(x)
        else:
            b[i] = x

    ans = len(b)

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = [int(input()) for i in range(n)]
m = 10**9
X = []
for a in A:
    i = bisect.bisect_right(X, -a)
    if i == len(X):
        X.append(-a)
    else:
        X[i] = -a
print(len(X))

Submission status: Accepted

Solution code:
N = int(input())
A = [-1*int(input()) for _ in range(N)]


def LIS(seq, wider_sense=False):
    from bisect import bisect_left, bisect_right
    f = bisect_right if wider_sense else bisect_left
    N = len(seq)
    INF = 10**18
    dp = [INF] * (N+1)
    for x in seq:
        i = f(dp, x)
        dp[i] = x
    return f(dp, INF-1)


answer = LIS(A, wider_sense=True)
print(answer)

Submission status: Accepted

Solution code:
import bisect
from collections import deque
N = int(input())
ans = deque()

for _ in range(N):
    a = int(input())
    ind = bisect.bisect_left(ans, a)
    if ind == 0:
        ans.appendleft(a)
    else:
        ans[ind-1] = a
print(len(ans))

Submission status: Accepted

Solution code:
import bisect
import collections
N = int(input())
A = [int(input()) for i in range(N)]
q = collections.deque([-1])
for x in A:
    id = bisect.bisect_left(q, x)
    # print(id, x, q)
    if id == 0:
        q.appendleft(x)
    else:
        q[id-1] = x
print(len(q))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
arr = []
from bisect import bisect
for a in A:
    i = bisect(arr, -a)
    if i == len(arr):
        arr.append(-a)
    else:
        arr[i] = -a
print(len(arr))

Submission status: Accepted

Solution code:
n = int(input())
al = []
for _ in range(n):
    a = int(input())
    al.append(-a)


def LIS(L):
    from bisect import bisect
    seq = []
    for i in L:
        pos = bisect(seq, i)
        if len(seq) <= pos:
            seq.append(i)
        else:
            seq[pos] = i
    return len(seq)


print(LIS(al))

Submission status: Accepted

Solution code:
def examA():
    N, M = LI()
    l = 1; r = N
    for _ in range(M):
        L, R = LI()
        l = max(L,l)
        r = min(R,r)
    ans = max(0,r-l+1)
    print(ans)
    return

def examB():
    N = I()
    S = [I()for _ in range(N)]
    rest = []
    for s in S:
        if s%10==0:
            continue
        rest.append(s)
    if sum(S)%10==0:
        if not rest:
            print(0)
            return
        ans = sum(S) - min(rest)
    else:
        ans = sum(S)
    print(ans)
    return

def examC():
    N, K = LI()
    K -= 1
    A = LI()
    L = A.index(1)
    #print(L)
    ans = (N-1+K-1)//K
    print(ans)
    return

def examD():
    def ketadp(a):
        n = len(a)
        dp = defaultdict(int)
        dp[0, 0, 0, 0, 0] = 1
        for i, less, has3, has5, has7 in itertools.product(range(n), (0, 1), (0, 1), (0,1), (0,1)):
            max_d = 7 if less else int(a[i])
            for d in range(max_d + 1):
                if d==0 and has3==0 and has5==0 and has7==0:
                    dp[i + 1, 1, has3, has5, has7] += dp[i, less, has3, has5, has7]
                if not (d==3 or d==5 or d==7):
                    continue
                less_ = less or d < max_d
                has3_ = has3 or d == 3
                has5_ = has5 or d == 5
                has7_ = has7 or d == 7
                dp[i + 1, less_, has3_, has5_, has7_] += dp[i, less, has3, has5, has7]

        ans = sum(dp[n, less, 1, 1, 1] for less in (0, 1))
        return ans
    N = SI()
    ans = ketadp(N)
    print(ans)
    return

def examE():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    for a in A[1:]:
        cur = bisect.bisect_left(que,a)
        if cur==0:
            que.appendleft(a)
        else:
            que[cur-1] = a
    ans = len(que)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

# dp[k]:最適に部分列を繋げた時の集合
dp = deque([seq[0]])

for i in range(1,len(seq)):
    if seq[i] <= dp[0]:
        dp.appendleft(seq[i])

    else:
        dp[bisect.bisect_left(dp, seq[i])-1] = seq[i]

print(len(dp))

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

d = deque()
d.append(a[-1])
for i in reversed(range(N-1)):
	if a[i] >= d[-1]:
		d.append(a[i])
	else:
		index = bisect.bisect_right(d,a[i])
		d[index] = a[i]

print(len(d))

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

LIS = deque([a[0]])
for i in range(1,N):
    if a[i] > LIS[-1]:
    	LIS[-1] = a[i]
    elif LIS[0] >= a[i]:
    	LIS.appendleft(a[i])
    else:
    	LIS[bisect.bisect_left(LIS, a[i])-1] = a[i]

print(len(LIS))

Submission status: Accepted

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

def binsearch(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] < threshold:
            right = mid
        else:
            left = mid
    return right


last=[]
for val in A:
    temp = binsearch(val, last)
    if temp == len(last):
        #last.insert(0, val)
        last.append(val)
    else:
        last[temp] = val
    #print(last)
print(len(last))

Submission status: Accepted

Solution code:
from collections import deque
import bisect

N = int(input())
L = [int(input()) for _ in range(N)]
Q = deque()
Q.append(L[0])

for l in L[1:]:
    r = bisect.bisect_left(Q, l)
    if r == 0:
        Q.appendleft(l)
    else:
        Q[r-1] = l
print(len(Q))

Submission status: Accepted

Solution code:
import bisect

n = int(input())

c = []
for i in range(n):
    a = int(input())
    j = bisect.bisect_right(c, -a)
    if j == len(c):
        c.append(-a)
    else:
        c[j] = -a
print(len(c))

Submission status: Accepted

Solution code:
def sub():
  import sys
  input = sys.stdin.readline
  n = int(input())
  a1 = int(input())
  a = [a1]
  ap = a.append
  for _ in range(n-1):
    ai = int(input())
    if ai <= a[-1]:
      ap(ai)
    elif ai > a[0]:
      a[0] = ai
    else:
      h = 0
      l = len(a)-1
      while l-h>1:
        m = (l+h)//2
        if ai > a[m]:
          l = m
        else:
          h = m
      a[l] = ai
  print(len(a))   
sub()

Submission status: Accepted

Solution code:
from bisect import bisect_right

N, *A = map(int, open(0).read().split())

INF = 10 ** 10
dp = [INF] * N
for i in range(N):
    dp[bisect_right(dp, -A[i])] = -A[i]

print(max(i + 1 for i, v in enumerate(dp) if v < INF))

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = []
    for i in range(N):
        A.append(iip(False))

    maxes = [1]
    nc = 1
    for a in A:
        idx = bisect_right(maxes, -a)
        #print(idx, a)
        #print(maxes)
        if idx == nc:
            maxes.append(-a)
            nc += 1
        else:
            maxes[idx] = -a

    print(nc)

#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N = int(input())
A = [int(input()) for _ in range(N)]
Min = [A[-1]]
for i in range(N - 2, -1, -1):
    temp = bisect.bisect_right(Min, A[i])
    if temp == len(Min):
        Min.append(A[i])
    elif Min[temp] != A[i]:
        Min[temp] = A[i]
    elif temp + 1 != len(Min):
        Min[temp + 1] = A[i]
    else:
        Min.append(A[i])
print(len(Min))

Submission status: Accepted

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
import bisect
B=[]
C=A[::-1]
for i in C:
  a=bisect.bisect_right(B,i)
  if a==len(B):
    B.append(i)
  else:
    B[a]=i
print(len(B))

Submission status: Accepted

Solution code:
N=int(input())
from collections import deque
d = deque([int(input())]) 
import bisect

for i in range(N-1):
  a=int(input())
  if a>d[-1]:
    d[-1]=a
  elif d[0]>=a:
    d.appendleft(a)
  else:
    i=bisect.bisect_left(d,a)
    d[i-1]=a
print(len(d))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# sequence decomposing
import bisect
n = int(input())
lists = [int(input()) for _ in range(n)]
lists = lists[::-1]
dataset = []
dataset.append(lists[0])
# datasetは単調増加なリストの値
for i in range(1, n):
    x = lists[i]
    if x >= dataset[-1]:
        dataset.append(x)
    elif x < dataset[-1]:
        index = bisect.bisect_right(dataset, x)
        dataset[index] = x
print(len(dataset))

Submission status: Accepted

Solution code:
from bisect import bisect_right
N = int(input())
A = [int(input()) for _ in range(N)]
dp = [10**10] * N
for a in A:
    a = -a
    dp[bisect_right(dp, a)] = a
ans = N - dp.count(10**10)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

import bisect

# from collections import Counter, deque

# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math


# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = [-int(readline()) for _ in range(n)]

    c = [1] * n

    for number in a:
        idx = bisect.bisect_right(c, number)
        c[idx] = number

    ans = bisect.bisect_left(c, 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

import bisect

dp = [-1]*(n+1)

for i in range(n):
  v = int(input())
  l = bisect.bisect_left(dp, v)
  if l==n+1:
    l -= 1
  if dp[l]<v:
    dp[l] = v
  else:
    dp[l-1] = v

cnt = 0
for i in range(n, 0, -1):
  if dp[i]>=0:
    cnt += 1
  else:
    break
    
print(cnt)

Submission status: Accepted

Solution code:
#134_E
import bisect
n=int(input())
a=[int(input()) for _ in range(n)][::-1]

LIS = [a[0]]
for i in range(1, n):
    if a[i] >= LIS[-1]:
        LIS.append(a[i])
    else:
        LIS[bisect.bisect_right(LIS, a[i])] = a[i]

print(len(LIS))

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc134/tasks/abc134_e
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    A = [int(input()) for _ in range(N)]
    d = deque()
    for i in A:
        pos = bisect_left(d, i)
        if pos == 0:
            d.appendleft(i)
        else:
            d[pos-1] = i
    print(len(d))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
from collections import deque

n = int(input())
la = [int(input()) for _ in range(n)]
result = deque([])

for a in la:
    idx = bisect.bisect_left(result, a)
    if idx==0:
        result.appendleft(a)
    else:
        result[idx - 1] = a
print(len(result))

Submission status: Accepted

Solution code:
import bisect
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

NUM = deque()
NUM.appendleft(A[0])

A = A[1:]


for a in A:
    if a <= NUM[0]:
        NUM.appendleft(a)
    else:
        i = bisect.bisect_left(NUM, a)
        NUM[i-1] = a


print(len(NUM))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
ans = [-1*int(input())]
for i in range(n-1):
  a=int(input())
  a=-1*a
  if ans[-1]<=a:
    ans.append(a)
  else:
    b = bisect.bisect_right(ans,a)
    ans[b]=a
print(len(ans))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left, bisect_right

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# dp と bisect.insort
N = ir()
INF = 10 ** 12
dp = [INF] * (N+1)
for _ in range(N):
    a = ir()
    i = bisect_right(dp, -a)
    dp[i] = -a

print(bisect_left(dp, INF))
# 18

Submission status: Accepted

Solution code:
N=int(input())
ans=[]
m=10**10
for i in range(0,N):
    a=int(input())
    if m>=a:
        ans.append(a)
        m=a
    else:
        start=0
        end=len(ans)-1
        while end-start>1:
            test=(end+start)//2
            if a>ans[test]:
                end=test
            else:
                start=test
        if a>ans[start]:
            ans[start]=a
            if start==len(ans)-1:
                m=a
        else:
            ans[end]=a
            if end==len(ans)-1:
                m=a

print(len(ans))

Submission status: Accepted

Solution code:
from bisect import bisect_right
n=int(input())
a=[int(input()) for _ in range(n)]
a=a[::-1]
lis=[a[0]]
for i in range(1,n):
  if lis[-1]<=a[i]:
    lis.append(a[i])
  else:
    inde=bisect_right(lis,a[i])
    lis[inde]=a[i]
print(len(lis))