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 _ in range(N)]

dp = [-A[0]]
def solve():
    import bisect
    for i in range(1, N):
        a = bisect.bisect_left(dp, -A[i]+0.1) #入れるべき場所
        # print (a)
        if a == len(dp):
            dp.append(-A[i])
        else:
            dp[a] = -A[i]
        # print (dp)
    return len(dp)


print (solve())

Submission status: Accepted

Solution code:
import sys
from collections import deque
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N = int(input())
    a = int(input())
    q = deque()
    q.append(a)
    ans = 1
    for _ in range(N-1):
        n = int(input())
        if n <= q[0]:
            q.appendleft(n)
            ans += 1
            continue

        if n > q[-1]:
            q[-1] = n
            continue

        pos = bisect_left(q, n)
        q[pos-1] = n
        min_ = q[0]

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
import sys
import bisect
input = sys.stdin.readline

n = int(input())
#####単位元######
ide_ele = -1

#num:n以上の最小の2のべき乗
num =2**((n-1).bit_length())
seg=[ide_ele]*(2*num)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res
    
def main():
    used = defaultdict(int)
    a = [int(input()) for i in range(n)]
    b = sorted(a)
    for i in range(n):
        a[i] = bisect.bisect_left(b,a[i])
    
    tank = [a[0]]
    used[a[0]] = 1
    update(a[0],a[0])
    
    for i in range(1,n):
        while True:
            if used[tank[0]] > 0:
                break
            else:
                heapq.heappop(tank)
        #塗り替え
        if tank[0] < a[i]:
            ma = query(0,a[i])
            
            used[ma] -= 1
            heapq.heappush(tank,a[i])
            used[a[i]] += 1
            if used[ma] == 0:
                update(ma,-1)
        else:
            heapq.heappush(tank,a[i])
            used[a[i]] += 1
        update(a[i],a[i])

    res = 0
    for e in tank:
        if used[e] > 0:
            res += 1
            used[e] -= 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
from collections import deque
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    As = [int(stdin.readline().rstrip()) for x in range(N)]
    dq = deque([])
    for A in As:
        idx = bisect.bisect_left(dq, A)
        if idx == 0:
            dq.appendleft(A)
        else:
            dq[idx - 1] = A
    print(len(dq))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect
N, *A = map(int, open(0).read().split())
D = [1]*(N+1)
D[0] = -10**10

for a in A:
    idx = bisect(D, -a)
    D[idx] = min(D[idx], -a)
print(bisect(D, 0)-1)

Submission status: Accepted

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

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

maxims = [A[0]]
ans = 1
for a in A[1:]:
    if maxims[-1] > a:
        idx = bisect.bisect(maxims,a)
        maxims[idx] = a
    else:
        maxims.append(a)
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *

input=sys.stdin.readline

def f(n):
    mi=-1
    r = [inf]*n
    for _ in range(n):
        a = -int(input())
        i = bisect_right(r, a)
        r[i]=a
        if i>mi:
            mi=i
    print(mi+1)

n = int(input())
inf=10**10
f(n)

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
P = [-e for e in set(A)]
P.sort()
P.append(1)
MP = {e: i for i, e in enumerate(P)}
N += 1

data = [0]*(N+1)
def get(k):
    r = 0
    while k:
        r += data[k]
        k -= k & -k
    return r
def add(k, x):
    while k <= N:
        data[k] += x
        k += k & -k
N0 = 2**(N-1).bit_length()
def lower_bound(x):
    w = i = 0
    k = N0
    while k:
        if i+k <= N and w + data[i+k] <= x:
            w += data[i+k]
            i += k
        k >>= 1
    return i+1

for a in A:
    j = MP[-a]
    i = lower_bound(get(j+1))
    if i != N+2:
        add(i, -1)
    add(j+1, 1)
print(get(N))

Submission status: Accepted

Solution code:
# 広義最長部分増加数列の長さを求めるdef
# 配列LIS自体は広義最長部分増加文字列ではない
import bisect
def lis(seq):
    LIS = [seq[0]]
    for i in range(1, len(seq)):
        if seq[i] >= LIS[-1]:
            LIS.append(seq[i])
        else:
            LIS[bisect.bisect_right(LIS, seq[i])] = seq[i]
    return(len(LIS))

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

b = a[::-1]
print(lis(b))

Submission status: Accepted

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

import bisect
from collections import deque

temp = deque()
temp.appendleft(A[0])
for i in range(1,N):
  if temp[0] >= A[i]:
    temp.appendleft(A[i])
  else:
    temp[bisect.bisect_left(temp,A[i])-1] = A[i]
print(len(temp))

Submission status: Accepted

Solution code:
import bisect

n=int(input())
arr=[int(input()) for _ in range(n)]
num=1
ans=[-arr[0]]
for i in range(1,n):
  if -arr[i]>=ans[-1]:
    ans.append(-arr[i])
    num+=1
  else:
    pos=bisect.bisect_right(ans,-arr[i])
    ans[pos]=-arr[i]
print(num)

Submission status: Accepted

Solution code:
import bisect

n=int(input())
arr=[int(input()) for _ in range(n)]
num=1
ans=[-arr[0]]
for i in range(1,n):
  if -arr[i]>=ans[-1]:
    ans.append(-arr[i])
  else:
    pos=bisect.bisect_right(ans,-arr[i])
    ans[pos]=-arr[i]
print(len(ans))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = [int(input()) for i in range(n)]
answer = []

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

print(len(answer))

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

# 解は最長非増加部分列の長さ
dp = [-1 for _ in range(N)]
for a in A:
    dp[bisect_left(dp, a) - 1] = a
ans = sum(x >= 0 for x in dp)

print(ans)

Submission status: Accepted

Solution code:
import bisect

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

def LIS(A):
    """
    returns Longest Increasing Subsequence of list A.
    """
    B = [A[0]]
    for i in range(N-1):
        if A[i+1] >= B[-1]:
            B.append(A[i+1])
        else:
            index = bisect.bisect_left(B, A[i+1])
            B[index] = A[i+1]
    return B

def LDS(A):
    """
    returns Longest Decreasing Subsequence of list A.
    """
    A = A[::-1]
    B = [A[0]]
    for i in range(N-1):
        if A[i+1] >= B[-1]:
            B.append(A[i+1])
        else:
            index = bisect.bisect_right(B, A[i+1])
            B[index] = A[i+1]
    return B[::-1]


print(len(LDS(A)))

Submission status: Accepted

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

import heapq

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

B = []

for a in A:
    i = bisect.bisect_right(B, a)
    if i != len(B):
        B[i] = a
    else:
        B.append(a)

# print(B)
print(len(B))

pass

Submission status: Accepted

Solution code:
def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
print(m)

Submission status: Accepted

Solution code:
import bisect

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

B = [A[N - 1]]
for i in reversed(range(0, N - 1)):
  if A[i] >= B[-1]:
    B.append(A[i])
  else:
    index = bisect.bisect_right(B, A[i])
    B[index] = A[i]
print(len(B))

Submission status: Accepted

Solution code:
import bisect
a=[-int(input()) for _ in [0]*int(input())]
dp=[]
for x in a:
    i = bisect.bisect(dp,x)
    if i == len(dp):
        dp.append(x)    
    else:            
        dp[i] = min(dp[i],x)
print(len(dp))

Submission status: Accepted

Solution code:
import bisect
import collections
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
m = collections.deque([])
for i in range(0, n):
    j = bisect.bisect_left(m, a[i])
    if j == 0:
        m.appendleft(a[i])
    else:
        m[j - 1] = a[i]
print(len(m))

Submission status: Accepted

Solution code:
import sys
aa=list(map(int,sys.stdin.read().split()))
aa=aa[1:aa[0]+1]
n=len(aa)
import bisect
bb=[]
for i in range(n):
    if not bb:
        bb.append(aa[-i-1])
    else:
        if bb[-1] <= aa[-i-1]:
            bb.append(aa[-i-1])
        else:
            j = bisect.bisect_right(bb,aa[-i-1])
            bb[j] = aa[-i-1]
print(len(bb))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC134 E
 
import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7
 
n = int(input())
a = [int(input()) for _ in range(n)]
m = []
for i in range(n):
    r = bisect.bisect_right(m,-a[i])
    if r == len(m):
        m.append(-a[i])
    else:
        m[r] = -a[i]
print(len(m))

Submission status: Accepted

Solution code:
from bisect import*
n,*a=map(int,open(0))
b=bisect
c=[-1]*n
for a in a:c[b(c,a-1)-1]=a
print(n-b(c,-1))

Submission status: Accepted

Solution code:
import io
import sys
from bisect import bisect_right, bisect_left
from collections import deque


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
7
1
0
3
4
1
2
1
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()

  l = deque([IN_I()])

  for i in range(0, n - 1):
    num = IN_I()

    idx = bisect_left(l, num)
    if idx == 0:
      l.appendleft(num)
    else:
      l[idx - 1] = num
    # print(l)

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Accepted

Solution code:
import bisect as bs
N = int(input())
A = [int(input()) for _ in range(N)]
def LDS(a):
    N = len(a)
    INF = float("inf")
    dp = [-INF]*N
    dp[N-1] = a[0]
    for i in range(1, N):
        j = bs.bisect_left(dp, a[i])-1
        dp[j] = a[i]
    for i in range(N-1, -1, -1):
        if dp[i] == -INF:
            return N-i-1
    return N
print(LDS(A))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque
N = int(input())
A = [int(input()) for i in range(N)]
cnt, ms, flag = 1, deque(), 1
ms.append(A[0])
for a in A[1:]:
    if a <= ms[0]:
        ms.appendleft(a)
        cnt += 1
    else:
        i = bisect_left(ms, a)-1
        ms[i] = a
print(cnt)

Submission status: Accepted

Solution code:
from bisect import bisect
inf = float('inf')

# 広義単調増加
def LIS(arr):
    N = len(arr)
    dp = [inf] * N
    res = 0
    for a in arr:
        pos = bisect(dp,a)
        dp[pos] = a
        res = max(res, pos + 1)
    return res

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

ans = LIS(A[::-1])
print(ans)

Submission status: Accepted

Solution code:
import bisect
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N = int(input())
    A = deque([int(input())])
    for k in range(N-1):
        t = int(input())
        if A[0] >= t:
            A.appendleft(t)
        else:
            A[bisect.bisect_left(A,t)-1] = t
    print(len(A))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC134 E

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = [-int(input()) for _ in range(N)]
tmp = [A[0]]
for i in A[1:N]:
    index = bisect.bisect(tmp, i)
    if index == len(tmp):
        tmp.append(i)
    else:
        tmp[index] = i

print(len(tmp))

Submission status: Accepted

Solution code:
from bisect import*
n,*a=map(int,open(0))
b=[-1]*n
for a in a:b[bisect(b,a-1)-1]=a
print(n-b.count(-1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect

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


LIS = list()
for i in a:
    j = bisect.bisect_right(LIS, i)
    if len(LIS) == j:
        LIS.append(i)
    else:
        LIS[j] = i

print(len(LIS))

Submission status: Accepted

Solution code:
from collections import deque
import bisect

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

colors = deque()
for i in range(N):
    index = bisect.bisect_left(colors, A[i])
    if index == 0:
        colors.appendleft(A[i])
    else:
        colors[index - 1] = A[i]
print(len(colors))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from bisect import bisect_right, bisect_left
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    d = deque()
    for a in A:
        t = bisect_right(d, a)
        if t == 0:
            d.appendleft(a)
            continue
        if d[t-1] == a:
            t = bisect_left(d, a)
        if t == 0:
            d.appendleft(a)
        else:
            d[t-1] = a
    print(len(d))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
from collections import deque
from bisect import bisect_right, bisect_left
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    d = deque()
    for a in A:
        t = bisect_right(d, a)
        if t == 0:
            d.appendleft(a)
            continue
        if d[t-1] == a:
            t = bisect_left(d, a)
        if t == 0:
            d.appendleft(a)
        else:
            d[t-1] = a
    print(len(d))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
an = [0]*n
for i in range(0, n):
    an[i] = int(input())
dp = [-1] * n

len = 1
dp[0] = an[0]
for i in range(1,n):
    if dp[len-1] >= an[i]:
        dp[len] = an[i]
        len += 1
        continue
    
    idx = len // 2
    r = len-1
    l = 0
    while(True):
        if dp[idx] >= an[i]:
            if r == idx+1:
                dp[r] = an[i]
                break
            else:
                l = idx
                idx = idx + (r - idx) // 2
        else:
            if l == idx:
                dp[l] = an[i]
                break
            else:
                r = idx
                idx = l + (idx - l) // 2
    
print(len)

Submission status: Accepted

Solution code:
from collections import deque
import bisect

def solve():
  N = int(input())
  A = [int(input()) for i in range(N)]
  q = deque()
  for a in A:
    if len(q) == 0 or a <= q[0]:
      q.appendleft(a)
    else:
      q[bisect.bisect_left(q, a) - 1] = a

  return len(q)

print(solve())

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = [10**10 - int(input()) for i in range(N)]
INF = 10**12

dp = [INF for i in range(N+1)]
#print(A,dp)

for a in A:
    i = bisect.bisect_right(dp,a)
    dp[i] = a
#print(dp)
res = bisect.bisect_left(dp,INF)
print(res)

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left
inf = float('inf')


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

color = deque()

for a in A:
    pos = bisect_left(color, a)
    if pos == 0:
        color.appendleft(a)
    else:
        color[pos-1] = a

ans = len(color)
print(ans)

Submission status: Accepted

Solution code:
"""
A = a1,a2,a3,a4,...
同じ色のとき、i<jならai<aj

が成り立つときの最小の色の数
"""

from bisect import bisect_right

prev = 10**9+7
cnt = 0
As = [-prev]
n = int(input())
for _ in range(n):
    a = int(input())
    update = bisect_right(As,-a)
    if update-1 == cnt:
        As.append(-a)
        cnt += 1
    else:
        As[update] = -a 
    prev = a

print(cnt)

Submission status: Accepted

Solution code:
"""
A = a1,a2,a3,a4,...
同じ色のとき、i<jならai<aj

が成り立つときの最小の色の数

2 1 4 5 3

8
5 
4 
3 
2 
1 
3 
2 
1

5
4
3
2 3
1 2
1



"""

from bisect import bisect_right

prev = 10**9+7
cnt = 0
As = [-prev]
n = int(input())
for _ in range(n):
    a = int(input())
    update = bisect_right(As,-a)
    if update-1 == cnt:
        As.append(-a)
        cnt += 1
    else:
        As[update] = -a 
    prev = a

print(cnt)

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

b = deque([])
for a in A:
  if len(b) == 0:
    b.append(a)
  else:
    if a <= b[0]:
      b.appendleft(a)
    else:
      b[bisect.bisect_left(b, a) - 1] = a
print(len(b))

Submission status: Accepted

Solution code:
import bisect
import collections

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

ans = collections.deque([A[0]])

for a in A[1:]:
    if a <= ans[0]:  # 色を増やすしかない
        ans.appendleft(a)
    else:  # 既存の色のどこかに追加
        idx = bisect.bisect_left(ans, a)
        ans[idx-1] = a
    # print(a, ans)

# print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left
inf = float('inf')


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

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

for a in A[1:]:
    pos = bisect_left(color, a)
    if pos == 0:
        color.appendleft(a)
    else:
        color[pos-1] = a

ans = len(color)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

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

b = deque([])

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b.appendleft(ai)
        else:
            idx = bisect_left(b, ai)
            b[idx-1] = ai

print(len(b))

Submission status: Accepted

Solution code:
from collections import deque
import bisect

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


b = deque([])

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b.appendleft(ai)
        else:
            index = bisect.bisect_left(b, ai)
            b[index-1] = ai

print(len(b))

Submission status: Accepted

Solution code:
import collections, bisect

def resolve():

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

    d = collections.deque()

    for i in range(n):
        change_index = bisect.bisect_left(d, ai[i]) - 1
        if change_index == -1:
            d.appendleft(ai[i])
        else:
            d[change_index] = ai[i]

    print(len(d))
    
resolve()

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

color = [-1]*N

for i in range(N):
    pos = bisect_left(color, A[i])
    color[pos-1] = A[i]

ans = len([c for c in color if c != -1])
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

color = [-1]*N

ans = 0
l = N

for i in range(N):
    pos = bisect_left(color, A[i])
    if pos == l:
        ans += 1
    color[pos-1] = A[i]

ans = len([c for c in color if c != -1])
print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())

def bisect_right_reverse(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return hi


c = []
for i in range(N):
    n = int(input())
    index = bisect_right_reverse(c,n)
    #print(index)
    if index == len(c):
        c.append(n)
    else:
        c[index] = n
    #print(c)

print(len(c))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs,math,heapq as hq
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

def LIS(L):
  L = L[::-1]
  LIS=[]
  for i in L:
    pos = bs.bisect_right(LIS,i) 
    if len(LIS) <= pos:
      LIS.append(i)
    else:
      LIS[pos]=i
  return len(LIS)

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())


print(LIS(a))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from bisect import bisect_right
n=int(input())
A=[-int(input()) for _ in range(n)]
LIS=[]
for a in A:
    idx=bisect_right(LIS,a)
    if idx==len(LIS):
        LIS.append(a)
    else:
        LIS[idx]=a
print(len(LIS))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from bisect import bisect_right
n=int(input())
A=[-int(input())-1 for _ in range(n)]
M=[0]*n
for a in A:
    idx=bisect_right(M,a)
    M[idx]=a
print(sum(m!=0 for m in M))

Submission status: Accepted

Solution code:
import bisect
from collections import deque
N=int(input())
a=[int(input()) for _ in range(N)]
d=deque()

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

Submission status: Accepted

Solution code:
import bisect as bs
import collections

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

col = collections.deque()
min_ = 10000000000

for a in alist:
    if a <= min_:
        col.appendleft(a)
    else:
        index = bs.bisect_left(col, a) - 1
        col[index] = a
    min_ = col[0]

print(len(col))

Submission status: Accepted

Solution code:
import sys
import numpy as np

pin = np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep='\n')
N = pin[0]
a = pin[1:]
b = -1 -a
c = np.zeros(N, dtype=np.int32)
for d in b:
    i = np.searchsorted(c, d, side='right')
    c[i] = d

print((c < 0).sum())

Submission status: Accepted

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

from bisect import bisect_left, bisect_right  # 二分探索
from collections import deque  # 双方向キュー

def main_ok():
    N = i2n()
    A = ii2nn(N)
    B = [1]
    for a in A:
        t = bisect_right(B, -a)
        if t < len(B):
            B[t] = -a
        else:
            B.append(-a)
    print(len(B))

def main():
    N = i2n()
    A = ii2nn(N)
    B = deque()
    B.appendleft(-1)
    for a in A:
        t = bisect_left(B, a)
        if t > 0:
            B[t-1] = a
        else:
            B.appendleft(a)
    print(len(B))

main()

Submission status: Accepted

Solution code:
import bisect
def LIS():
    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:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

def LISDesc():
    L[0] = A[-1]
    length = 1
    for i in range(N-2, -1, -1):
        if L[length-1] <= A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_right(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

INFTY = 10**13
N = int(input())
A = [int(input()) for i in range(N)]
L = [INFTY for i in range(N)]
ans = LISDesc()
print(ans)

Submission status: Accepted

Solution code:
#quoted LIS from https://qiita.com/python_walker/items/d1e2be789f6e7a0851e5
import bisect

n=int(input())
arr=[int(input()) for _ in range(n)][::-1]
LIS=[arr[0]]
for i in range(1,n):
  if arr[i]>=LIS[-1]:
    LIS.append(arr[i])
  else:
    LIS[bisect.bisect_right(LIS,arr[i])]=arr[i]
print(len(LIS))

Submission status: Accepted

Solution code:
from bisect import bisect as bl

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

def lds(X: list):
    L = [-X[0]]
    for x in X[1:]:
        if L[-1] <= -x:
            L.append(-x)
        else:
            L[bl(L, -x)] = -x
    return len(L)

print(lds(A))

Submission status: Accepted

Solution code:
import bisect

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

A.reverse()
ans = [A[0]]

for i in range(1, N):
    n = bisect.bisect_right(ans, A[i])
    if A[i] >= ans[-1]:
        ans.append(A[i])
    else:
        ans[n] = A[i]

print(len(ans))

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque
n = int(input())
A=[int(input()) for _ in range(n)]
q=deque()
for a in A:
    i=bisect_left(q,a)
    if not i:
        q.appendleft(a)
    else:
        q[i-1]=a
print(len(q))

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right,bisect
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
LIS = []
for i in range(N):
    a =- int(input())
    idx = bisect(LIS,a)
    if idx == len(LIS):
        LIS.append(a)
    else:
        LIS[idx]=a
print(len(LIS))

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

c = [0] * n
end = n

for ai in a:
    ci = bisect_left(c, ai, end, n)
    c[ci - 1] = ai
    if ci <= end:
        end -= 1
print(n - end)

Submission status: Accepted

Solution code:
import bisect

N = input()
N = int(N)
S = [-int(input()) for _ in range(N)]
result = []

for i in range(N):
    hoge = bisect.bisect(result,S[i])
    if hoge == len(result):
        result.append(S[i])
    else:
        result[hoge] = S[i]
print(len(result))

Submission status: Accepted

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

r = [-1]*N

mind = float("inf")
for n in range(N):
    ind = bisect.bisect_left(r, a[n])
    r[ind-1] = a[n]
    mind = min(mind, ind)

# print(r)
print(N-mind+1)

Submission status: Accepted

Solution code:
def binary_search(A,func):
    l = 0
    r = len(A)-1
    if func(0,A):return -1
    if not func(r,A):return r
    while l+1<r:
        i = (l+r)//2
        if func(i,A):
            r = i
        else:
            l = i
    return l

N = int(input())
A = [int(input()) for _ in [0]*N]
B = [A[0]]
ans = 1
for a in A[1:]:
    r = binary_search(B,lambda i,b:b[i]<a)+1
    if r < ans:B[r] = a
    else:
        B.append(a)
        ans+=1
print(ans)

Submission status: Accepted

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

color = deque([a.pop(0)])
color_count =0 
for ai in a: 
    index = bisect.bisect_left(color, ai)
    if index > 0:
        color[index -1] = ai
    else:
        color.appendleft(ai)
print(len(color))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_right, bisect_left
N = int(input())
a_list = [int(input()) for _ in range(N)]

color_list = [1]
for a in a_list:
    a *= -1
    index = bisect_right(color_list, a)
    if index < len(color_list):
        color_list[index] = a
    else:
        color_list.append(a)
#     print(color_list, a)
print(len(color_list))

Submission status: Accepted

Solution code:
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
res = []
res.append(0 - dat[0])

import bisect

for i in range(1, n):
    #print(res)
    a = bisect.bisect_right(res, 0 - dat[i])
    #print("a={0}".format(a))

    if a == len(res):
        res.append( (0 - dat[i]) )
    else:
        res[a] = (0 - dat[i])

print(len(res))