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:
N=int(input())
A=[int(input()) for i in range(N)]
from bisect import bisect_left
from collections import deque
l=deque()
for a in A:
    i=bisect_left(l,a)
    if i==0:
        l.appendleft(a)
    else:
        l[i-1]=a
print(len(l))

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
N = int(input())
X = [-1] * N
for _ in range(N):
    a = int(input())
    i = br(X, a-1) - 1
    X[i] = a

print(N - X.count(-1))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect

n = int(input())
aaa = list(map(int, sys.stdin.readlines()))

dp = [1]
for a in aaa:
    a *= -1
    i = bisect(dp, a)
    if i < len(dp):
        dp[i] = a
    else:
        dp.append(a)
print(len(dp))

Submission status: Accepted

Solution code:
from collections import *
import sys
inp = raw_input

def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

def lis(X):
    N = len(X)
    P = [0]*N
    M = [0]*(N+1)
    L = 0
    for i in range(N):
        lo, hi = 1, L + 1
        while lo < hi:
            mid = (lo + hi) >> 1
            if X[M[mid]] >= X[i]:
                lo = mid + 1
            else:
                hi = mid
        newL = lo
        P[i] = M[newL - 1]
        M[newL] = i
        L = max(L, newL)
    S = [0]*L
    k = M[L]
    for i in range(L-1, -1, -1):
        S[i] = X[k]
        k = P[k]
    return S

N = ni()
A = [ni() for _ in range(N)]

print(len(lis(A)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect

INF = 10 ** 18
N = int(input())
A = [10 ** 10 - int(input()) for _ in range(N)] # 逆順にしておく

# 最長単調減少列：狭義

dp = [INF] * (N+1) # 長さ、その長さの末端としてありうる最大値

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

answer = bisect.bisect_left(dp, INF)
print(answer)

Submission status: Runtime Error

Solution code:
N = int(input())
seq = [int(input()) for _ in range(N)]
from collections import deque
LIS = deque([seq[0]])
for i in range(1,len(seq)):
    if seq[i] <= LIS[0]:
        LIS.appendleft(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i])-1] = seq[i]
print(len(LIS))

Submission status: Runtime Error

Solution code:
N = int(input())
seq = [int(input()) for _ in range(N)]
LIS = deque([seq[0]])
for i in range(1,len(seq)):
    if seq[i] <= LIS[0]:
        LIS.appendleft(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i])-1] = seq[i]
 
print(len(LIS))

Submission status: Runtime Error

Solution code:
import heapq
N = int(input())
A = list(int(input()) for _ in range(N))

S = [A[0]]
for i in range(1, N):
    if A[i] <= S[0]:
        S.insert(0, A[i])
        continue
    ok = 0
    ng = len(S)
    while ok+1 < ng:
        tmp = (ok+ng)//2
        if A[i] > S[tmp]:
            ok = tmp
        else:
            ng = tmp
    S[tmp] = A[i]
print(len(S))

Submission status: Runtime Error

Solution code:
from bisect import bisect

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

ans = [ma[0]]
for ai in ma[1:]:
    tmp = bisect(ans, ai)
    if tmp == len(ans):
        ans.append(ai)
    elif tmp < len(ans):
        ans[tmp] = ai
    print(ans)
print(len(ans))

Submission status: Runtime Error

Solution code:
from bisect import bisect

icase=1
if icase==1:
    n=int(input())
    a=[0]*n
    for i in range(n):
        a[i]=-int(input())
elif icase==2:
    n=5
    a=[-2,-1,-4,-5,-3]
elif icase==3:
    n=4
    a=[0,0,0,0]

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -10**10
    
    print(n,a,dp)
    for i in range(n):
#        idx = bisect(dp, a[i]-1)
        idx = bisect(dp, a[i])
        dp[idx] = min(a[i], dp[idx])
        print(i,idx,dp)

#        print("i:",i,"a:",a,"dp2:",dp2)            
    return dp

dp=loopa()        

print(bisect(dp, 10**10-1)-1)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import heapq
n=int(input())
l=[]
l.append(int(input()))
heapq.heapify(l)
for i in range(n-1):
    a=int(input())
    x=bisect_left(l,a)
    if x==0:
        heapq.heappush(l,a)
    else:
        l[x-1]=a
    print(l)
print(len(l))

Submission status: Runtime Error

Solution code:
from bisect import bisect

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

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -1
    dq = [0]*(n+1)    
    
#    print(n,a,dp)
    for i in range(n):
        idx = bisect(dp, a[i]-1)
        if dp[idx]==10**10:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i
            dp2=dp[1:idx+1]
            dq2=dq[1:idx+1]
        else:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i

    for i in range(len(dq2)-1,-1,-1):
        del a[dq2[i]]
#        print("i:",i,"a:",a,"dp2:",dp2)            

icnt=0
while len(a)>0:
    loopa()        
    icnt+=1

print(icnt)

Submission status: Runtime Error

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

n = int(input())
col_maxs = []
for _ in range(n):
    a = int(input()) * (-1)
    if not col_maxs:
        col_maxs.append(a)
        continue

    curr_max = col_maxs[-1]
    if a >= curr_max:
        col_maxs.append(a)
    else:
        # aより大きい最小要素のindex/value
        ind = bisect_right(col_maxs, a)
        col_maxs[ind] = a

print(len(col_maxs))

Submission status: Runtime Error

Solution code:
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):
    """value以下の最大の値を検索し、(index, value)の組を返す
    k: 着目しているノード (1-indexed)
    l: 探索区間 st[l, r) の左端 (0-indexed)
    r: 探索区間 st[l, r) の右端 (0-indexed)
    """
    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):
    """value以下の最大値を検索し、(index, value)の組を1つ返す
    見つからない場合は-1を返す
    """
    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)  # 以下を未満にするため-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))

Submission status: Runtime Error

Solution code:
# ABC134E

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    cho=[0]*(10**9+1)
    cho[A[0]]+=1
    maxset=set([A[0]])
    
    for i in range(1,N):
        remset=set()
        for m in maxset:
            if A[i]>m:
                remset.add(m)
            if A[i]==m:
                cho[m]+=1
        if len(remset)>0:
            maxset.remove(max(remset))
            maxset.add(A[i])
        else:
            maxset.add(A[i])
            
    print(max(len(maxset),max(cho)))
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
# ABC134E

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    cho=[0]*(10**5+1)
    cho[A[0]]+=1
    maxset=set([A[0]])
    
    for i in range(1,N):
        remset=set()
        for m in maxset:
            if A[i]>m:
                remset.add(m)
            if A[i]==m:
                cho[m]+=1
        if len(remset)>0:
            maxset.remove(max(remset))
            maxset.add(A[i])
        else:
            maxset.add(A[i])
            
    print(max(len(maxset),max(cho)))
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
# ABC134E

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    cho=[0]*(10**5+1)
    cho[A[0]]+=1
    maxset=set([A[0]])
    
    for i in range(1,N):
        remset=set()
        for m in maxset:
            if A[i]>m:
                remset.add(m)
            if A[i]==m:
                cho[m]+=1
        if len(remset)>0:
            maxset.remove(max(remset))
            maxset.add(A[i])
        else:
            maxset.add(A[i])
            
    print(maxset)
    print(max(len(maxset),cho))
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok
 
n = int(input())
li = [int(input()) for i in range(n)]
 
tmp = [li[0]]
minli = li[0]
 
for i in range(1,n):
    if li[i] <= minli:
        minli = li[i]
        tmp.append(li[i])
    else:
        idx = bisect_left_reverse(tmp,li[i])
        tmp[idx] = li[i]
 
print(len(tmp))

Submission status: Runtime Error

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

def LIS(L):
    dp = [L[0]]
    length = len(L)
    for i in range(1, length):
        print(dp)
        a = L[i]
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a
    return dp

print(len(LIS(As[::-1])))

Submission status: Runtime Error

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

def LIS(L):
    dp = [L[0]]
    length = len(L)
    lis = [[0]]*(length+1)
    l = 1
    for i in range(1, length):
        a = L[i]
        if a > dp[-1]:
            dp.append(a)
            l += 1
            lis[l] = dp[:]
        else:
            dp[bisect_left(dp, a)] = a
    for j in lis[l]:
        L.remove(j)
    return L

cnt = 0
while 1:
    L = LIS(As)
    cnt += 1
    if len(L)==0:
        print(cnt)
        break

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque

n = int(input())
lis = deque()

ans = 0
for i in range(n):
    a = int(input())
    if i == 0:
        lis.append(a)
        continue
    l = bisect.bisect_left(lis,a)
    r = bisect.bisect_right(lis,a)
    if l != r and l != 0:#同じものがある&更新できる色がないなら追加
        lis2 = list(lis)
        lis=deque(lis2[0:r]+[a]+lis[l:])

        
    elif l == 0:#最小値追加
        lis.appendleft(a)
    else:#最大値更新
        lis[r-1] = a
print(len(lis))

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque

n = int(input())
lis = deque()

ans = 0
for i in range(n):
    a = int(input())
    if i == 0:
        lis.append(a)
        continue
    l = bisect.bisect_left(lis,a)
    r = bisect.bisect_right(lis,a)
    if l != r and l != 0:#同じものがある&更新できる色がないなら追加
        lis.insert(r,a)
        
    elif l == 0:#最小値追加
        lis.appendleft(a)
    else:#最大値更新
        lis[r-1] = a
print(len(lis))

Submission status: Runtime Error

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

from collections import deque
from bisect import bisect_left

D = deque([])

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

print(len(D))

Submission status: Runtime Error

Solution code:
import bisect
def LIS(a):
    lis = [a[0]]
    for i in range(len(a)):
        if i != 0 and a[i] >= lis[-1]:
            lis.append(a[i])
        else:
            index = bisect.bisect_right(lis,a[i])
            lis[index] = a[i]
    return len(lis)

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_right

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

t = deque([-A[0]])
for a in A[1:]:
    if -a <= -t[0]:
        t.append(-a)
    else:
        t[bisect_right(t, -a)] = -a
print(len(t))

Submission status: Runtime Error

Solution code:
from random import random
from sys import setrecursionlimit

setrecursionlimit(10 ** 5)


class TreapNode:
    _value = None
    _priority = None
    _count = None
    _left = None
    _right = None

    def __init__(self, value):
        self._value = value
        self._priority = random()
        self._count = 1


def treap_rotate_right(n):
    l = n._left
    n._left = l._right
    l._right = n
    return l


def treap_rotate_left(n):
    r = n._right
    n._right = r._left
    r._left = n
    return r


def treap_insert(n, v):
    if n is None:
        return TreapNode(v)
    if v == n._right:
        n._count += 1
        return n
    if v < n._value:
        n._left = treap_insert(n._left, v)
        if n._priority > n._left._priority:
            n = treap_rotate_right(n)
    else:
        n._right = treap_insert(n._right, v)
        if n._priority > n._right._priority:
            n = treap_rotate_left(n)
    return n


def treap_delete(n, v):
    if n is None:
        return None
    if n._value > v:
        n._left = treap_delete(n._left, v)
        return n
    if n._value < v:
        n._right = treap_delete(n._right, v)
        return n

    # n._value == v
    if n._count > 1:
        n._count -= 1
        return n

    if n._left is None and n._right is None:
        return None

    if n._left is None:
        n = treap_rotate_left(n)
    elif n._right is None:
        n = treap_rotate_right(n)
    else:
        # n._left is not None and n._right is not None
        if n._left._priority < n._right._priority:
            n = treap_rotate_right(n)
        else:
            n = treap_rotate_left(n)
    return treap_delete(n, v)


def treap_size(n):
    if n is None:
        return 0
    return n._count + treap_size(n._left) + treap_size(n._right)


def treap_str(n):
    if n is None:
        return ""
    result = []
    if n._left is not None:
        result.append(treap_str(n._left))
    result.append("%d:%d" % (n._value, n._count))
    if n._right is not None:
        result.append(treap_str(n._right))
    return ' '.join(result)


def treap_search(n, v):
    # x 未満で最大のノードを検索する. n 未満のノードがなければ nil を返す
    if n is None:
        return None
    if n._value >= v:
        if n._left is None:
            return None
        return treap_search(n._left, v)
    # n._value < v
    if n._right is None:
        return n
    r = treap_search(n._right, v)
    if r is None:
        return n
    return r


class Treap:
    _root = None

    def insert(self, v):
        self._root = treap_insert(self._root, v)

    def delete(self, v):
        self._root = treap_delete(self._root, v)

    def __len__(self):
        return treap_size(self._root)

    def __str__(self):
        return treap_str(self._root)

    def search(self, v):
        return treap_search(self._root, v)


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

t = Treap()
for a in A:
    n = t.search(a)
    if n is not None:
        t.delete(n._value)
    t.insert(a)
print(len(t))

Submission status: Runtime Error

Solution code:
n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
l=deque([a[0]])
for i in range(1,n):
    if l[0]>=a[i]:
        l.appendleft(a[i])
    elif l[-1]<=a[i]:
        l.append(a[i])
    else:
        p=0
        q=len(l)-1
        while q-p!=1:
            if l[(p+q)//2]>=a[i]:
                q=(p+q)//2
            else:
                p=(p+q)//2
        l[p]=a[i]
print(len(l))

Submission status: Runtime Error

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*10**5
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Submission status: Runtime Error

Solution code:
from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
q=[0]*7**6
v=[[]for _ in q]
z=0
for a,b in t:v[a-1]+=[b]
for i in v[:M]:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)

Submission status: Runtime Error

Solution code:
from heapq import*
(n,m),*t=[map(int,s.split())for s in open(0)]
q=[0]*7**6
v=[[]for _ in q]
z=0
for a,b in t:
  v[a-1]+=[b]
for i in v[:m]:
  for j in i:
    heappush(q,-j)
  z-=heappop(q)
print(z)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys

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

LIS = [1]
n, *A = map(int, read().split())

for a in A:
    a *= -1
    if LIS[-1] <= a:
        LIS.append(a)
    else:
        LIS[bisect_right(LIS, a)] = a
print(len(LIS))

Submission status: Runtime Error

Solution code:
import bisect
import sys
input = sys.stdin.readline
N = int(input())
A = []
for n in range(N):
    A.append(int(input()))
A = A[::-1]
INF = int(1e+9 + 10)
lis = [INF]* (N)
for n in range(N):
    i = bisect.bisect(lis, A[n])    
    lis[i] = A[n]
    #print (lis)
print (bisect.bisect_left(lis, INF)) a

Submission status: Runtime Error

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

import bisect

q = []
for i, Ai in enumerate(A):
    if i == 0:
        ans = 1
        q.append(Ai)
        continue
    #
    idx = bisect.bisect_right(q, Ai)
    if idx + 1 >= len(q):
        q.append(Ai)
    else:
        q[idx + 1] = AI
    #
    print("#", q, ans)

print(len(q))

Submission status: Runtime Error

Solution code:
#E
from collections import deque
import bisecit
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: Runtime Error

Solution code:
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[]
for a in A:
    i=bisect.bisect_left(color,a)
    if i==0:
        color+=[a]
    else:
        color[i]=a
        color.sort()
print(len(color))

Submission status: Runtime Error

Solution code:

class Node:
    def __init__(self, data): #コンストラクタ
        self.data = data #ノードがもつ数値
        self.left = None #左エッジ
        self.right = None #右エッジ
N = int(input())
A = [int(input()) for i in range(N)]
G = [Node(A[0])]
def rec(g,ni):
    if g.data < ni.data:
        if g.right is None:
            g.right = ni
        else:
            rec(g.right,ni)
    else:
        if g.left is None:
            g.left = ni
        else:
            rec(g.left,ni)

for i in range(1,N):
    Ni = Node(A[i])
    rec(G[0],Ni)
    G.append(Ni)
ans = 1
g = G[0]
while True:
    if g.left is None:
        break
    else:
        g = g.left
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
seq = []
for i in range(n):
    a = int(input())
    seq.append(a)
reverse(seq)

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))

Submission status: Runtime Error

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)
        if idx == nc:
            maxes.append(a)
        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: Runtime Error

Solution code:
N=int(input())
from collections import deque
d = deque([int(input())]) 
def insert_search(List,a,l,r):
  if r==l:
    List[l-1]=a
    return List
  m=(l+r)//2
  if List[m]<a:
    return insert_search(List,a,m+1,r)
  elif List[m]!=a:
    return insert_search(List,a,l,m-1)
  else:
    while List[m]==a:
      m-=1
    List[m]=a
    return List
for i in range(N-1):
  a=int(input())
  if a>d[-1]:
    d[-1]=a
  elif d[0]>=a:
    d.appendleft(a)
  else:
    d=insert_search(d,a,0,len(d)-1)
print(len(d))

Submission status: Runtime Error

Solution code:
N=int(input())
X=[int(input())]

def insert_search(List,a,l,r):
  if r==l:
    List[l-1]=a
    return List
  m=(l+r)//2
  if List[m]<a:
    return insert_search(List,a,m+1,r)
  elif List[m]!=a:
    return insert_search(List,a,l,m-1)
  else:
    while List[m]==a:
      m-=1
    List[m]=a
    return List
for i in range(N-1):
  a=int(input())
  if a>X[-1]:
    X[-1]=a
  elif X[0]>=a:
    X.insert(0,a)
  else:
    X=insert_search(X,a,0,len(X)-1)
print(len(X))

Submission status: Runtime Error

Solution code:
N=int(input())
X=[int(input())]

def insert_search(List,a,l,r):
  if r==l:
    List[l-1]=a
    return List
  m=(l+r)//2
  if List[m]<a:
    return insert_search(List,a,m+1,r)
  elif Lisr[m]!=a:
    return insert_search(List,a,l,m-1)
  else:
    while List[m]==a:
      m-=1
    List[m]=a
    return List
for i in range(N-1):
  a=int(input())
  if a>X[-1]:
    X[-1]=a
  elif X[0]>=a:
    X.insert(0,a)
  else:
    X=insert_search(X,a,0,len(X)-1)
print(len(X))

Submission status: Runtime Error

Solution code:
n=int(input())
A=[]
for i in range(n):
    A.append(int(input()))
ans=1
for i in range(n-1):
    if A[i]>=A[i+1]:
        m=A[i]
        break
for i in range(n-1):
    if A[i]>=A[i+1]:
        m=min(m,A[i])
    if A[i+1]<=m:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

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

s = deque([a[0]])

from bisect import bisect_right

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

# print(s)
print(len(s))

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc134/tasks/abc134_e
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 = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = array('q' sorted(ls))  # insertを爆速にするためにarray型にします。signed long long 前提です

    # 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)
        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):
        '''
        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_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            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:
        # bstのなかで、aより小さく且つ一番大きい要素をaに書き換えていく
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))