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 bisect import bisect_right

N = int(input())
A = [int(input()) for _ in range(N)]
INF = float('inf')

dp = [-A[0]]
cnt = 1
for i in range(1, N):
    a = -A[i]
    idx = bisect_right(dp, a)
    if idx == cnt:
        dp.append(a)
        cnt += 1
    else:
        dp[idx] = a

print(cnt)

Submission status: Accepted

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

X = deque([])

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


print(len(X))

Submission status: Accepted

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

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


print(len(X))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=[int(input()) for i in range(n)]
data=collections.deque()
for i, ai in enumerate(A):
    k=bisect.bisect_left(data,ai)
    if k==0:
        data.appendleft(ai)
    else:
        data[k-1]=ai
print(len(data))

Submission status: Accepted

Solution code:

import bisect


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

  tail = []
  len_tail = 0
  for ai in a:
    idx = bisect.bisect_right(tail, -ai, lo=0, hi=len_tail) 
    if idx == len_tail:
      tail.append(-ai)
      len_tail += 1
    else:
      tail[idx] = - ai

  print(len_tail )


if __name__ == "__main__":
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect


class Deque:
    def __init__(self, src_arr=[], max_size=300000):
        self.N = max(max_size, len(src_arr)) + 1
        self.buf = list(src_arr) + [None] * (self.N - len(src_arr))
        self.head = 0
        self.tail = len(src_arr)

    def __index(self, i):
        l = len(self)
        if not -l <= i < l: raise IndexError('index out of range: ' + str(i))
        if i < 0:
            i += l
        return (self.head + i) % self.N

    def __extend(self):
        ex = self.N - 1
        self.buf[self.tail + 1: self.tail + 1] = [None] * ex
        self.N = len(self.buf)
        if self.head > 0:
            self.head += ex

    def is_full(self):
        return len(self) >= self.N - 1

    def is_empty(self):
        return len(self) == 0

    def append(self, x):
        if self.is_full(): self.__extend()
        self.buf[self.tail] = x
        self.tail += 1
        self.tail %= self.N

    def appendleft(self, x):
        if self.is_full(): self.__extend()
        self.buf[(self.head - 1) % self.N] = x
        self.head -= 1
        self.head %= self.N

    def pop(self):
        if self.is_empty(): raise IndexError('pop() when buffer is empty')
        ret = self.buf[(self.tail - 1) % self.N]
        self.tail -= 1
        self.tail %= self.N
        return ret

    def popleft(self):
        if self.is_empty(): raise IndexError('popleft() when buffer is empty')
        ret = self.buf[self.head]
        self.head += 1
        self.head %= self.N
        return ret

    def __len__(self):
        return (self.tail - self.head) % self.N

    def __getitem__(self, key):
        return self.buf[self.__index(key)]

    def __setitem__(self, key, value):
        self.buf[self.__index(key)] = value

    def __str__(self):
        return 'Deque({0})'.format(str(list(self)))


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

x = Deque()

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.appendleft(a)
        else:
            x[r - 1] = a

print(len(x))

Submission status: Accepted

Solution code:
import bisect
import  collections

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

x = collections.deque()

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.appendleft(a)
        else:
            x[r - 1] = a

print(len(x))

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    d = deque([])
    d.append(A[0])
    for i in range(1,N):
        p = bisect_left(d, A[i])
        if p == 0:
            d.appendleft(A[i])
        else:
            d[p-1] = A[i]

    print(len(d))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
dp = [float('inf')]*n
for i in range(n):
  c = a[n-i-1]
  b = bisect.bisect_right(dp,c)
  if dp[b] > c:
    dp[b] = c
print(bisect.bisect_right(dp,10**9+1))

Submission status: Accepted

Solution code:
import bisect

N = int(input())

A = []

for i in range(N):

    a = int(input())
    A.append(a)

A.reverse()

seq = [float("-inf")]

for i in A:

    ind = bisect.bisect_right(seq,i)

    if ind == len(seq):
        seq.append(i)
    else:
        seq[ind] = i

print (len(seq)-1)

Submission status: Accepted

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

from collections import deque
import bisect

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

print(len(d))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
def bisect_rev(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    t = []
    for a in A:
        k = bisect_rev(t, a)
        if k == len(t):
            t.append(a)
        else:
            t[k] = a
    return len(t)

print(main())

Submission status: Accepted

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

b = [a[-1]]
for i in range(n - 2, -1, -1):
    if b[-1] <= a[i]:
        b.append(a[i])
    else:
        b[bisect.bisect_right(b, a[i])] = a[i]

print(len(b))

Submission status: Accepted

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

#weakly increase
def LIS(L):
    INF = float('inf')
    DP = [INF]*(N+1)

    def bisect(v):
        if v<DP[0]:
            return 0
        l = 0
        r = N
        while r-l>1:
            if v<DP[(l+r)//2]:
            #if v<=DP[(l+r)//2]:
                r = (l+r)//2
            else:
                l = (l+r)//2
        return r
    
    for v in L:
        DP[bisect(v)] = v
    return DP

DP = LIS(A)
count = 0
for i in range(N):
    if DP[i]<10**10:
        count+=1
    else:
        break
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_right
from collections import deque

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

c, ans = deque(), 0

for i in range(n):   
    t = bisect_right(c, a[i]-1) - 1
    if t < 0: c.appendleft(a[i])
    else: c[t] = a[i]

print(len(c))

Submission status: Accepted

Solution code:
import bisect

n = int(input())
# bisectが昇順のリストにしか対応していないのでマイナスをかける。
# -> ansの順序が昇順で管理できるようになる。最小値をans[-1]で管理する。
A = [- int(input()) for _ in range(n)]

ans = [A[0]]
for a in A[1:]:
  # ansの最小値以下の数値 -> append, else: a > ans[?] を満たす左端の?の値を書き換える。
  if a >= ans[-1]:
    ans.append(a)
  else:
    pos = bisect.bisect_right(ans, a) 
    ans[pos] = a 
print(len(ans))

Submission status: Accepted

Solution code:
import bisect

n = int(input())
# bisectが昇順のリストにしか対応していないのでマイナスをかける。
# -> ansの順序が昇順で管理できるようになる。最小値をans[-1]で管理する。
A = [- int(input()) for _ in range(n)]

num = 1
ans = [A[0]]
for a in A[1:]:
  # ansの最小値以下の数値 -> append, else: a > ans[?] を満たす左端の?の値を書き換える。
  if a >= ans[-1]:
    ans.append(a)
    num += 1
  else:
    pos = bisect.bisect_right(ans, a) 
    ans[pos] = a 
print(num)

Submission status: Accepted

Solution code:
#6484898
from bisect import bisect
N= int(input())
A = []
for i in range(N):
    t = int(input())
    A.append(t)

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
N = int(input())
seq = [-int(input()) for i in range(N)] 
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]
print(len(LIS))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import bisect
N = int(input())
a = [-int(input()) for i in range(N)]
ls = []
res = 0
for elem in a:
    idx = bisect.bisect_right(ls,elem)
    if idx == res:
        ls.append(elem)
        res += 1
    else:
        ls[idx] = elem
print(res)

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

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

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

Submission status: Accepted

Solution code:
import sys

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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

import bisect
from collections import deque


def main():
	n=int(input())
	A=[int(input()) for _ in range(n)]
	
	Q=deque([A[0]])
	
	for i in range(1,n):
		if A[i]<=Q[0]:
			Q.appendleft(A[i])

		else:
			ix=bisect.bisect_left(Q,A[i])
			Q[ix-1]=A[i]
	
	print(len(Q))
	
	
	
	
	



if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import bisect

n = int(input())

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

ary = []
ary.append(a[0])

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

Submission status: Accepted

Solution code:
import bisect
n = int(input())
A = [int(input()) for _ in range(n)]
L = [-1]*n
count = 0
for i in A:
  t = bisect.bisect_left(L, i) - 1
  if L[t] == -1:
    count += 1
  L[t] = i
print(count)

Submission status: Accepted

Solution code:
n=int(input())
# 降順のリストで二分探索
# 自分より小さい数字で最も大きいものを自分でアップデート
# 該当がなければ最後に追加
d=[]
d.append(int(input()))
for i in range(n-1):
  a=int(input())
  ok=len(d)
  ng=-1
  while abs(ok-ng)>1:
    mid=abs(ok+ng)//2
    if d[mid]<a:
      ok=mid
    else:
      ng=mid
  if ok==len(d):
    d.append(a)
  else:
    d[ok]=a
print(len(d))

Submission status: Accepted

Solution code:
#新しい値が最小なら追加，そうでなければそれを超えない最大の値を書き換え
#降順なので，10**10から引くことで逆転させておく
#→新しい値が最大なら追加，そうでなければそれを超える最小の値を書き換え
import bisect

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

b=[]
b.append(A[0])

for i in range(1,N):
    index=bisect.bisect_right(b,A[i])
    if index==len(b):
        b.append(A[i])
    else:
        b[index]=A[i]
print(len(b))

Submission status: Accepted

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


#新しい値が最小なら追加，そうでなければそれを超えない最大の値を書き換え
#降順
b=[]
b.append(A[0])


def bi_s(n):
    if b[-1]>=n:
        return -1
    if n>b[0]:
        return 0
    
    ceil=0
    floor=len(b)-1
    med=1#len(b)==2のとき
    while abs(floor-ceil)>1:
        med=(ceil+floor)//2
        if n>b[med]:
            floor=med
        else:
            ceil=med
    return floor

for i in range(1,N):
    index=bi_s(A[i])
    if index==-1:
        b.append(A[i])
    else:
        b[index]=A[i]
print(len(b))

Submission status: Accepted

Solution code:
import sys
from collections import deque
import time
import bisect
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=[int(input()) for i in range(n)]
# print(a)
ans=deque([a[0]])
for i in range(1,n):
    loc=bisect.bisect_left(ans,a[i])
    if loc==0:
        ans.appendleft(a[i])
    else:
        ans[loc-1]=a[i]
# print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline
n = int(input())
a = [int(input()) for i in range(n)]
ans = 0
color = [a[n-1]]
for i in range(n-2,-1,-1):
    if a[i]>=color[-1]:
        color.append(a[i])
    else:
        x = bisect.bisect_right(color,a[i])
        color[x] = a[i]
print(len(color))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
from collections import deque

N = int(input())
A = deque([-1])

for i in range(N):
  a = int(input())
  idx = bisect.bisect_left(A, a)
  if idx == 0:
    A.appendleft(a)
  
  else:
    A[idx-1] = a

print(len(A))

Submission status: Accepted

Solution code:
import bisect

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

Submission status: Accepted

Solution code:
import bisect
from collections import deque
n=int(input())
A=deque([int(input())])

for i in range(n-1):
  a=int(input())
  b=bisect.bisect_left(A,a,lo=0,hi=len(A))
  if b==0:
    A.appendleft(a)
  else:
    A[b-1]=a
print(len(A))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)
q = deque([])

for i,j in enumerate(a):
  if i == 0:
    q.append(j)
    continue
  c = bisect.bisect_left(q,j)
  if c == 0:
    q.appendleft(j)
  else:
    q[c-1] = j
    
print(len(q))

Submission status: Accepted

Solution code:
import collections
from collections import deque
import bisect

n=int(input())
a=list(int(input()) for i in range(n))
b=deque()
b.append(-1)


for i in range(n):
    if a[i]>b[0]:
        x=bisect.bisect_right(b,a[i]-1)
        b[x-1]=a[i]
    else:
        b.appendleft(a[i])
print(len(b))

Submission status: Accepted

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


n = int(input())
color_box = deque([-1])

for _ in range(n):
    num = int(input())
    idx = bisect.bisect_left(color_box, num)
    if idx == 0:
        color_box.appendleft(num)
    else:
        color_box[idx-1] = num

print(len(color_box))

Submission status: Accepted

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

q=[]

def bisect_desc(a,x):
    r = len(a)
    if r == 0:
        return 0
    l = 0
    while l != r:
        f = (l+r)//2
        if a[f] >= x:
            l = f+1
        else:
            r = f
    return l

for sa in a:
    t = bisect_desc(q,sa)
    if t ==len(q):
        q.append(sa)
    else:
        q[t] = sa

print(len(q))

Submission status: Accepted

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

q=[]

def bisect_desc(a,x):
    r = len(a)
    if r == 0:
        return 0
    l = 0
    while l != r:
        f = (l+r)//2
        if a[f] >= x:
            l = f+1
        else:
            r = f
    return l

for sa in a:
    t = bisect_desc(q,sa)
    if t ==len(q):
        q.append(sa)
    else:
        q[t] = sa

print(len(q))

Submission status: Accepted

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

q=[]
def bisect_desc(a,x):
    r = len(a)
    if r == 0:
        return 0
    l = 0
    while l != r:
        f = (l+r)//2
        if a[f] >= x:
            l = f+1
        else:
            r = f
    return l

for sa in a:
    t = bisect_desc(q,sa)
    if t ==len(q):
        q.append(sa)
    else:
        q[t] = sa

print(len(q))

Submission status: Accepted

Solution code:
#from bisect import bisect_right as right
import bisect

#import sys
#readline = sys.stdin.buffer.readline

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

INF = 10**10
dp = [INF] * (N+1)

answer = 0
for a in A:
  r = bisect.bisect_right(dp, a)
  if dp[r] > a:
    if dp[r] == INF:
      answer += 1
    dp[r] = a
print(answer)

Submission status: Accepted

Solution code:
from bisect import bisect_right as right

#import sys
#readline = sys.stdin.buffer.readline

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

INF = 10**10
dp = [INF] * (N+1)

answer = 0
for a in A:
  r = right(dp, a)
  if dp[r] > a:
    if dp[r] == INF:
      answer += 1
    dp[r] = a
print(answer)

Submission status: Accepted

Solution code:
from bisect import bisect_right as right
import sys
readline = sys.stdin.buffer.readline

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

INF = 10**10
dp = [INF] * (N+1)

answer = 0
for a in A:
  r = right(dp, a)
  if dp[r] > a:
    if dp[r] == INF:
      answer += 1
    dp[r] = a
print(answer)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque


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

	top = deque([A[0]])
	for a in A[1:]:
		if top[0] >= a:
			top.appendleft(a)
		else:
			index = bisect_left(top, a)
			top[index-1] = a
	
	print(len(top))


if __name__ == '__main__':
	solve()

Submission status: Accepted

Solution code:
import bisect
from collections import deque
n = int(input())
color = deque([int(input())])
for i in range(1,n):
    num = int(input())
    if color[0] >= num:
        color.appendleft(num)
    else:
        bis = bisect.bisect_left(color, num)
        color[bis-1] = num
print(len(color))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
from bisect import bisect_left

def solve(N: int, A: "List[int]"):
    b = deque([A[0]])
    for a in A[1:]:
        if a <= b[0]:
            b.appendleft(a)
        else:
            idx = bisect_left(b, a)
            b[idx-1] = a
    print(len(b))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = IR(n)
LIS = deque([A[0]])
for i in range(1, n):
    if A[i] <= LIS[0]:
        LIS.appendleft(A[i])
    else:
        LIS[bisect_left(LIS, A[i]) - 1] = A[i]


print(len(LIS))

Submission status: Accepted

Solution code:
import sys
import bisect

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [10 ** 10 - ri() for _ in range(N)]
l = []
for a in A:
    i = bisect.bisect_right(l, a)
    if i == len(l):
        l.append(a)
    else:
        l[i] = a

print(len(l))
#39

Submission status: Accepted

Solution code:
import sys
import bisect

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
INF = 10 ** 18
A = [10 ** 10 - ri() for _ in range(N)]
dp = [INF] * (N+1)
for a in A:
    i = bisect.bisect_right(dp, a)
    dp[i] = a

print(bisect.bisect_left(dp, INF))
#39 答え見る

Submission status: Accepted

Solution code:
from bisect import bisect_right

N = int(input())
S = [1]

for _ in range(N):
    a = int(input())
    a *= -1
    i = bisect_right(S, a)

    if i == len(S):
        S.append(a)
    else:
        S[i] = a

print(len(S))

Submission status: Accepted

Solution code:
#%%
import bisect

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

ans_list = [-1] * n
for i in range(n):
    tmp = bisect.bisect_left(ans_list, a[i])
    #print(tmp)
    if tmp == 0:
        ans_list.insert(0, a[i])
    else:
        ans_list[tmp-1] = a[i]
    #print(ans_list)

ans = 0
for i in range(n):
    if ans_list[i] != -1:
        ans += 1
print(ans)

Submission status: Accepted

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

N = int(input())
# 逆順にする
A = [int(input()) for _ in range(N)][::-1]

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

# 広義単調増加列の長さの最大値を求める
# https://mathtrain.jp/tantyou
for a in A:
    idx = bisect.bisect_right(dp, a)
    dp[idx] = a

answer = bisect.bisect_left(dp, float("inf"))
print(answer)

Submission status: Accepted

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

N = int(input())
# 逆順にする
A = [int(input()) for _ in range(N)][::-1]

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

# 狭義単調増加列の長さの最大値を求める
for a in A:
    idx = bisect.bisect_right(dp, a)
    dp[idx] = a

answer = bisect.bisect_left(dp, float("inf"))
print(answer)

Submission status: Accepted

Solution code:
import bisect
import collections


def sequence_decomposing(N: int, A: list)->int:
    mins = collections.deque([A[0]])

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

    return len(mins)


if __name__ == "__main__":
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = sequence_decomposing(N, A)
    print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

LDS = deque()
LDS.append(A[0])

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

print(len(LDS))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect
def resolve():
    n=int(input())
    A=[-int(input()) for _ in range(n)]
    Q=[]
    for a in A:
        i=bisect(Q,a)
        if(i==len(Q)): Q.append(a)
        else: Q[i]=a

    print(len(Q))
resolve()

Submission status: Accepted

Solution code:
from bisect import bisect_left
n=int(input())
x=[-1]*n
for _ in range(n):
    a=int(input())
    i=bisect_left(x,a)-1
    x[i]=a
print(n-x.count(-1))

Submission status: Accepted

Solution code:
from bisect import bisect 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 bisect
from collections import deque

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

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

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
for i in a[n-2::-1]:
  if c[-1] <= i:
    c.append(i)
  else:
    c[bisect.bisect_left(c,i+1)] = i
  #print(c)
print(len(c))

Submission status: Accepted

Solution code:
import bisect
from collections import deque
n = int(input())
a = [0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
count = deque()
count.append(a[0])
for i in range(1, n):
    
    index = bisect.bisect_left(count, a[i])
    
    if index == 0:
        count.appendleft(a[i])
    else:
        count[index - 1] = a[i]
    #print("{}  {}".format(count, index))
print(len(count))

Submission status: Accepted

Solution code:
import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

print(count)

Submission status: Accepted

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

L=[-1]*N
for i in A:
    n=bisect_left(L,i)
    L[n-1]=i

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

Submission status: Accepted

Solution code:
from bisect import bisect_right

N = int(input())
A = [int(input()) for _ in range(N)]
B = [A[-1]]
ans = 1
for a in reversed(A[:-1]):
    idx = bisect_right(B, a)
    if idx == ans:
        B.append(a)
        ans += 1
    else:
        B[idx] = a
print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import deque

n = int(input())
l = deque([int(input())])

for i in range(1, n):
  a = int(input())
  p = bisect.bisect_left(l,a)
  if p == 0:
    l.appendleft(a)
  else:
    l[p-1] = a

print(len(l))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]
memo = []
ans = 0

def reverse_binary_serch(target, query):
    l = 0
    r = len(target) - 1
    while True:
        if r - l < 2:
            if target[l] < query:
                return l
            else:
                return r
        i = (l + r) // 2
        if target[i] >= query:
            l = i
        else:
            r = i

for ai in a:
    if not memo or memo[-1] >= ai:
        memo.append(ai)
    else:
        index = reverse_binary_serch(memo, ai)
        memo[index] = ai

print(len(memo))

Submission status: Accepted

Solution code:
import bisect
import sys
import collections
input = sys.stdin.readline
N = int(input())
A = [int(input()) for i in range(N)]
B = [A[0]]
B = collections.deque(B)
tmp = [0]*N
ans = 1
for i in range(1, N):
    id = bisect.bisect_left(B, A[i])
    if id == 0:
        B.appendleft(A[i])
    else:
        B[id-1] = A[i]
print(len(B))

Submission status: Accepted

Solution code:
import bisect
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n = ri()
ls = ris(n)
ls = [-x for x in ls]

dp = [float('inf')] * n
for x in ls:
    dp[bisect.bisect_right(dp, x)] = x
print(bisect.bisect_left(dp, float('inf')))

Submission status: Accepted

Solution code:
import bisect
n=int(input())
seq=[]
for i in range(n):
    seq.append(int(input()))
seq.reverse()
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]

print(len(LIS))

Submission status: Accepted

Solution code:
import bisect

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

B=[]
c=0
for a in A:
  p=bisect.bisect_right(B,a)
  if p==c:
    B.append(a)
    c += 1
  else:
    B[p]=a

print(len(B))

Submission status: Accepted

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


n = int(input())
A = [int(input()) for _ in range(n)]
A = A[::-1]
color = [10**10]

for a in A:
    idx = bisect.bisect_right(color, a)
    if idx < len(color):
        color[idx] = a
    else:
        color.append(a)

print(len(color))

Submission status: Accepted

Solution code:
import bisect


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)][::-1]
    ans = [A[0], ]
    bright = bisect.bisect_right
    L = 1
    for i, a in enumerate(A):
        if i == 0:
            continue
        index = bright(ans, a)
        if index == L:
            ans.append(a)
            L += 1
        else:
            ans[index] = a
    print(L)


if __name__ == "__main__":
    main()