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:
# -*- coding: utf-8 -*-
from math import sqrt
from itertools import accumulate
from collections import Counter
from heapq import heappop, heappush
from bisect import bisect, bisect_left
import sys

input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))


class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.node = [0]*(self.size + 1)
 
    def initialize(self, S):
        # S[0] = 0にしておく
        # 1-indexed
        if len(S) < self.size + 1:
            S += [S[-1]] * (self.size+1 - len(S))
        for i in range(1, self.size+1):
            self.node[i] = S[i] - S[i - (i&-i)]
 
    def sum(self, i):
        res = 0
        while i:
            res += self.node[i]
            i -= (i & -(i))
        return res
 
    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.node[i] += x
            i += (i & -(i))
 
    def bisect_left(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] < x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1
 
    def bisect(self, x):
        res = 0
        tmp = 0
        b = 2**(int.bit_length(self.size)-2)
        while b:
            if tmp + self.node[res+b] <= x:
                res += b
                tmp += self.node[res]
            b //= 2
        return res + 1


class DammySet:

    def __init__(self, counter, INF=2**32, counter_is_unique_and_sorted=True, filled=1):
        if not counter_is_unique_and_sorted:
            if type(counter) != Counter:
                counter = Counter(counter)

            self.bit = BIT(len(counter.keys())+3)
            self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
            self.val = [counter[k] for k in self.key]
            S = list(accumulate(self.val))
            self.bit.initialize(S)

        else:
            self.bit = BIT(len(counter) + 3)
            self.key = [-INF] * (len(counter) + 3)
            self.key[-1] = INF
            self.val = [0] * (len(counter) + 3)
            for i in range(2, len(counter)+2):
                self.key[i] = counter[i-2]
                self.val[i] = filled

            if filled:
                S = [0] * (len(counter) + 3)
                for i in range(2, len(counter)+2):
                    S[i] = i-1
                S[-1] = len(counter)
                self.bit.initialize(S)

    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

    def delete(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, -1)


    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)


    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)

    def find_lt(self, v):
        #'Find rightmost value less than x'
        rk = bisect_left(self.key, v) - 1
        rs = self.bit.sum(rk)
        return self.bit.bisect_left(rs)

    def find_gt(self, v):
        lk = bisect(self.key, v) - 1  # find rightmost value less than or equal to v
        ls = self.bit.sum(lk)
        return self.bit.bisect(ls) # find leftmost value greater than ls


    def find_ge(self, v):
        lk = bisect_left(self.key, v) - 1 # find rightmost value less than v
        ls = self.bit.sum(lk)
        return self.bit.bisect(ls) # find leftmost value greater than ls


    def pop_vals(self, l, r):
        assert l <= r

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1

        vix = 0
        rmvix = 0
        vals = [0]*delta
        rmvk = [0]*delta
        rmvv = [0]*delta
        while delta:
            OK = self.bit.bisect_left(tv)
            c = self.bit.sum(OK)
            d = c - tv + 1
            for _ in range(d):
                vals[vix] = self.key[OK]
                vix += 1
            rmvk[rmvix] = OK
            rmvv[rmvix] = d
            rmvix += 1
            tv += d
            tix = OK
            delta -= d

        for i in range(rmvix):
            self.bit.add(rmvk[i], -rmvv[i])
        return vals

N = int(input())
A = [int(input()) for _ in range(N)]
C = sorted(set(A))
dset = DammySet(C, filled=0)
L =  len(dset.bit.node) - 1

for i in range(N):
    ix = dset.find_lt(A[i])
    if ix > 1:
        dset.bit.add(ix, -1)
    dset.add(A[i])
    # print([dset.bit.sum(i+1) - dset.bit.sum(i) for i in range(L)])


print(dset.bit.sum(L))

Submission status: Accepted

Solution code:
N = int(input())
a = int(input())
l = [a]
d = {a: 1}
ans = 1
for _ in range(1, N):
    a = int(input())
    if a in d:
        d[a] += 1
        if l[-1] == a:
            ans += 1
        else:
            i = l.index(a) + 1
            v = l[i]
            if d[v] == 1:
                del d[v]
                l.remove(v)
            else:
                d[v] -= 1
    else:
        v = l[0]
        if v < a:
            if d[v] == 1:
                del d[v]
                l[0] = a
            else:
                d[v] -= 1
                l.insert(0, a)
        elif l[-1] > a:
            l.append(a)
            ans += 1
        else:
            left, right = 0, len(l) - 1
            while left + 1 != right:
                i = (left + right) // 2
                x = l[i]
                if x > a:
                    left = i
                else:
                    right = i
            v = l[right]
            if d[v] == 1:
                del d[v]
                l[right] = a
            else:
                d[v] -= 1
                l.insert(right, a)
        d[a] = 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
input = sys.stdin.readline
n = int(input().strip())
q = [-int(input().strip())]
qapp = q.append
bis_r = bisect.bisect_right
for i in range(n-1):
  a = -int(input().strip())
  if q[-1] <= a:
    qapp(a)
  else:
    b = bis_r(q,a)
    q[b] = a
print(len(q))

Submission status: Accepted

Solution code:
import sys
import bisect
from collections import deque
input = sys.stdin.readline
n = int(input().strip())
q = deque()
qappL = q.appendleft
for i in range(n):
  a = int(input().strip())
  b = bisect.bisect_left(q,a)
  if b == 0:
    qappL(a)
  else:
    q[b-1] = a
print(len(q))

Submission status: Accepted

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

Submission status: Accepted

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

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]

# dp[i] := 長さiの広義単調増加部分列を取る時の最大の数
dp = []
for a in A:
    i = bisect_right(dp, a)
    if i >= len(dp):
        dp.append(a)
    else:
        dp[i] = a

print(len(dp))

Submission status: Accepted

Solution code:
import bisect

N = int(input())

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

colors = []

for i in range(N-1, -1, -1):
    target = bisect.bisect_right(colors, A[i])

    if target == len(colors):
        colors.append(A[i])
    else:
        colors[target] = A[i]

print(len(colors))

Submission status: Accepted

Solution code:
#import bisect
def desc_bin(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it reverse-sorted assuming a
    is reverse-sorted.

    If x is already in a, insert it to the right of the rightmost x.

    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 lo
N=int(input())
ans=[]
for _ in range(N):
    num=int(input())
    
    index=desc_bin(ans,num)
    if index==len(ans):
        ans.append(num)
    else:
        ans[index]=num
    #print(ans)
print(len(ans))

Submission status: Accepted

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

a = list(map(lambda x: -x, a))
m = len(a)

lis = [float('inf')]*m

for x in a:
  lis[bisect.bisect_right(lis, x)] = x

print(len([x for x in lis if not (x == float('inf'))]))

Submission status: Accepted

Solution code:
import sys
import bisect
import collections


def input():
    return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    la = [int(input()) for _ in range(n)]
    result = collections.deque()
    for a in la:
        idx = bisect.bisect_left(result, a)
        if idx == 0:
            result.appendleft(a)
        else:
            result[idx - 1] = a
    print(len(result))


main()

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]
M = 10**9
color = []

for i in A:
    tmp = M-i
    if len(color) == 0:
        color.append(tmp)
    elif tmp >= color[-1]:
        color.append(tmp)
    else:
        color[bisect.bisect_right(color, tmp)] = tmp

print(len(color))

Submission status: Accepted

Solution code:
import bisect

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

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

print(ans)

Submission status: Accepted

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

import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

def LIS(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            # aがLの末尾以上なら増加部分列を延長する(今回は広義(=を含む))
            L.append(a)
        else:
            # そうでなければ、「a以下の最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_right(L, a)] = a
    return len(L)

# 後ろからLIS
print(LIS(A[::-1]))

Submission status: Accepted

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

import sys
from collections import deque
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def LDS(A: list):
    L = deque([A[0]])
    for a in A[1:]:
        if a <= L[0]:
            # Lの先頭よりaが小さければ減少部分列を延長する(今回は広義(=を含む))
            L.appendleft(a)
        else:
            # そうでなければ、「a以上の最小要素の手前」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_left(L, a)-1] = a
    return len(L)

N=INT()
A=[INT() for i in range(N)]

print(LDS(A))

Submission status: Accepted

Solution code:
import bisect
import collections

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

C = collections.deque()

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

print(len(C))

Submission status: Accepted

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

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

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
print(LIS(a[::-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import *
N = int(input())
A = [-int(input()) for i in range(N)]
dp = [float("inf")]*N
for a in A :
    ind = bisect_right(dp, a)
    dp[ind] = a
print(bisect_left(dp, float("inf")))

Submission status: Accepted

Solution code:
"""
賢過ぎる解法.汎用性が高そう.
"""
from bisect import bisect

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

data = [inputs[0]]
for i in range(1, N):
    index = bisect(data, inputs[i])
    if index == len(data):
        data.append(inputs[i])
    else:
        data[index] = inputs[i]

print(len(data))

Submission status: Accepted

Solution code:
import bisect
from collections import deque

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

colors = deque([])
colors.append(a_list[0])
for i in range(1, N):
    a = a_list[i]
    idx = bisect.bisect_left(colors, a)
    if idx == 0:
        colors.appendleft(a)
    else:
        colors[idx-1] = a

print(len(colors))

Submission status: Accepted

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

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

q = deque([A[0]])
for i in range(1,N):
    insert_index = bisect_left(q,A[i])
    if insert_index == 0:
        q.appendleft(A[i])
    else:
        q[insert_index-1] = A[i]

print(len(q))

Submission status: Accepted

Solution code:
import bisect
from collections import deque
def solve():
  n = int(input())
  a = [int(input()) for _ in range(n)]
  t = 1
  ans = deque([])
  for i,w in enumerate(a):
   if i == 0:
      ans.append(w)
   else:
    
    place = bisect.bisect_left(ans,w)
    if place == 0:
      ans.appendleft(w)
      t += 1
    else:
      ans[place-1] = w

  print(len(ans))
  
  
solve()

Submission status: Accepted

Solution code:
import bisect
 
n = int(input())
a = [int(input()) for _ in range(n)]
# それぞれの色の最大値を入れる筒のリスト
t = [a[-1]]
 
for i in reversed(a[:-1]):
    # それぞれの色のどの値よりも小さかったとき
    idx = bisect.bisect_left(t, i+1)
    # print(i, idx)
    if idx == len(t):
        t.append(i)
    # 効率的な色の探索
    else:
        t[idx] = i
    # print(t)
 
print(len(t))

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = [int(input()) for _ in range(n)]
# それぞれの色の最大値を入れる筒のリスト
t = [a[-1]]

for i in reversed(a[:-1]):
    # それぞれの色のどの値よりも小さかったとき
    idx = bisect.bisect_left(t, i+1)
    # print(i, idx)
    if idx == len(t):
        t.append(i)
    # 効率的な色の探索
    else:
        t[idx] = i
    # print(t)

print(len(t))

Submission status: Accepted

Solution code:
import bisect

N = int(input())

a = - int(input())

a_array = [a]

for i in range(N-1):
    a = - int(input())
    index = bisect.bisect_right(a_array,a)
    if index == len(a_array):
        a_array.append(a)
    else:
        a_array[index] = a
    # print(a_array)
print(len(a_array))

Submission status: Accepted

Solution code:
def bisect_right_descending(a, x, lo=0, hi=None):
    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 lo


n = int(input())

b = []

for i in range(n):
    a = int(input())
    c = bisect_right_descending(b,a)
    if c==len(b):
        b.append(a)
    else:
        b[c]=a

print(len(b))

Submission status: Accepted

Solution code:
"""
提出 #6475942 を参考に作成
"""

import bisect


def solve():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color_list = [A[-1]]
    for a in reversed(A[:-1]):
        # a より大きい数の中で一番小さい数の場所を取得する
        c = bisect.bisect_left(color_list, a + 1)
        if c == len(color_list):
            color_list.append(a)
        else:
            color_list[c] = a
    print(len(color_list))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from bisect import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
update_list=[11 for _ in range(n+1)]
for old_element in range(n):
    update_position=bisect(update_list,-a[old_element])
    update_list[update_position]=-a[old_element]

ans=0
while update_list[ans] <= 0:
	ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import deque

N = int(input())

tops = deque() 

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect

words = lambda t : list(map(t, input().split()))
n = int(input())
a = []
for i in range(n):
    a.append(-1 * int(input()))

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

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

print(len(b))

Submission status: Accepted

Solution code:
from bisect import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
dp = [1 for _ in range(n+2)]
for i in range(n):
	b = bisect(dp, -a[i])
	dp[b] = -a[i]
ans = 1
while dp[ans] <= 0:
	ans += 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque

n = int(input())
a = tuple(int(input()) for _ in range(n))

d = deque()

for ai in a:
    p = bisect_left(d, ai)  # aa以上の最小値のindex
    if p == 0:
        d.appendleft(ai)
    else:
        d[p - 1] = ai
ans = len(d)
print(ans)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
num_list = []
for i in range(n):
    num_list.append(int(input()) * -1) 

dp = [1] * n 

for i in num_list:
    indx = bisect.bisect_right(dp, i)
    dp[indx] = min(dp[indx], i)

ans = sum(x < 1 for x in dp)

print(ans)

Submission status: Accepted

Solution code:
def e_sequence_decomposing(N, A):
    # 求める解は、「与えられた数列の、単調非増加部分列の長さの最大値」
    # なので、「与えられた数列を逆にした数列の、単調非減少部分列の長さの最大値」
    # を求める。これは Longest Increasing Subsequence の考え方を援用できる。
    import bisect

    # lnds[k]: ある要素まで見たときにk+1個の非減少部分列が作れるもののうち、
    # 最も要素の値が小さいもの
    lnds = []  # Longest Non-Decreasing Subsequence

    for a in A[::-1]:
        idx = bisect.bisect_right(lnds, a)
        if idx == len(lnds):
            lnds.append(a)
        else:
            lnds[idx] = a
    return len(lnds)

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

Submission status: Accepted

Solution code:
n=int(input())
a_list=[int(input()) for i in range(n)]
a_list.reverse()
INF=10**10
dp=[INF]*n
import bisect
for i in range(n):
    a=a_list[i]
    x=bisect.bisect_right(dp,a)
    dp[x]=a
ans=0
for i in range(n):
    if dp[i]!=INF:
        ans=i+1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a_list=[int(input()) for i in range(n)]
a_list.reverse()
INF=10**10
dp=[INF]*n
import bisect
for i in range(n):
    a=a_list[i]
    x=bisect.bisect_right(dp,a)
    dp[x]=a
ans=0
for i in range(n):
    if dp[i]!=INF:
        ans=i+1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
N = int(input())
A = list(int(input()) for _ in range(N))
INF = 10 ** 9 + 1

dp = [INF]
for a in A:
    if -a >= dp[-1]:
        dp.append(-a)
    else:
        j = bisect_right(dp, -a)
        dp[j] = -a

print(len(dp))

Submission status: Accepted

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

input = sys.stdin.readline

def f(n):
    r = deque()
    for _ in range(n):
        a = int(input())
        i = bisect_left(r, a)
        if i:
            r[i - 1] = a
        else:
            r.appendleft(a)
    print(len(r))

n = int(input())
f(n)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys, math, bisect, random, itertools
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print(n*n*3)
    return

#B
def B():
    n, d = LI()
    print((n-1)//(2*d+1)+1)
    return

#C
def C():
    n = II()
    a = IR(n)
    b = a[::1]
    b.sort()
    for i in range(n):
        if a[i] == b[-1]:
            print(b[-2])
        else:
            print(b[-1])
    return

#D
def D():
    n = II()
    a = [0] + LI()
    for i in range(n // 2, 0, -1):
        x = sum(a[i::i])
        if x % 2 != a[i]:
            a[i] ^= 1
    ans = []
    x = 0
    for i in range(1, n + 1):
        if a[i]:
            ans.append(str(i))
            x += 1
    print(x)
    if x == 0:
        return
    print(" ".join(ans))
    return

#E
def E():
    n = II()
    a = IR(n)
    dp = deque([a[0]])
    ans = 1
    for i in a[1:]:
        x = bisect_right(dp, i)
        y = bisect_left(dp, i)
        if y == 0:
            ans += 1
            dp.appendleft(i)
        else:
            if x == y:
                dp[y - 1] = i
            else:
                if y >= ans:
                    ans += 1
                    dp.append(i)
                else:
                    dp[y - 1] = i
    print(ans)
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys

def DBsearch(L,x,narrow):
    n= len(L)
    if n==0: return 0
    if narrow and x in L: return L.index(x)
    last = L[-1]
    if x<last: return n
    if not narrow and x==last: return n
    #
    idx= -1
    i= 0
    j= n-1
    while j>=i:
        if i==j:
            if x>L[i]: idx= i
            break
        #
        mid= i + (j-i)//2
        if x<L[mid]:
            i= mid+1
        elif x==L[mid]:
            if narrow:
                idx= mid
                j  = mid - 1
            else:
                i = mid + 1
        else:
            idx= mid
            j= mid-1
    #
    return idx
#
def lds(L,narrow):
    seq= []
    for x in L:
        if len(seq)==0 or x<seq[-1]:
            seq.append(x)
        elif x==seq[-1]:
            if narrow:
                seq[DBsearch(seq,x,narrow)]= x
            else:
                seq.append(x)
        else:
            seq[DBsearch(seq,x,narrow)]= x
    #
    return len(seq)
#
n= int(sys.stdin.readline())
ai= [ int(sys.stdin.readline()) for _ in range(n) ]
print( lds( ai,False ) )

Submission status: Accepted

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

N=input()
A=[ int(sys.stdin.readline().strip())  for _ in range(N) ]

LIS=[]
for i,x in enumerate(A[::-1]):
	if i==0:
		LIS.append(x)
	elif LIS[-1]<=x:
		LIS.append(x)
	else:
		p=bisect_right(LIS,x)
		LIS[p]=x

print len(LIS)

Submission status: Accepted

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

N=input()
seq=[ int(sys.stdin.readline().strip())*-1  for _ in range(N) ]

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

print(len(LIS))

Submission status: Accepted

Solution code:
from bisect import *

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

r = [10**10] * N
index = -1
for i in range(N):
    j = bisect_right(r, -A[i])
    r[j] = -A[i]
    if j > index:
        index = j
print(index + 1)

Submission status: Accepted

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

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

l = deque()

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

print(len(l))

Submission status: Accepted

Solution code:
import bisect

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

Submission status: Accepted

Solution code:
import bisect

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

Submission status: Accepted

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

N=input()
A=[ int(sys.stdin.readline().strip())  for _ in range(N) ]

q=deque()

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

print len(q)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
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(): return list(sys.stdin.readline())[:-1]
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

#A
def A():
    n = I()
    print(3*n**2)
    return

#B
def B():
    n,d = LI()
    f = [1]*(n+2*d+2)
    ans = 0
    for i in range(n):
        if f[i]:
            for j in range(i,i+2*d+1):
                f[j] = 0
            ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    a = IR(n)
    mi = max(a)
    if a.count(mi) > 1:
        for i in range(n):
            print(mi)
    else:
        b = [a[i] for i in range(n)]
        b.sort()
        b = b[::-1]
        for i in range(n):
            if mi != a[i]:
                print(mi)
            else:
                print(b[1])

    return

#D
def D():
    n = I()
    a = LI()
    b = [0]*(n+1)
    for i in range(1,n+1)[::-1]:
        j = 2*i
        k = 0
        while j <= n:
            k ^= b[j]
            j += i
        if a[i-1]^k:
            b[i] = 1
    ans = []
    for i in range(n+1):
        if b[i]:
            ans.append(i)
    print(len(ans))
    if ans:
        print(*ans)
    return

#E
def E():
    n = I()
    a = IR(n)
    mi = [float("inf")]*(n+1)
    ans = 0
    for i in range(n):
        mi[bisect.bisect_right(mi,-a[i])] = -a[i]
    for i in range(n+1):
        if mi[i] == float("inf"):
            break
    print(i)
    return

#F
def F():
    n = I()

    return

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

Submission status: Accepted

Solution code:
from bisect import *

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

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

for i in range(N) :
    ind = bisect_right(dp, A[i])
    dp[ind] = A[i]

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

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())
    q = deque()
    for _ in range(N):
        a = int(input())
        pos = bisect_left(q, a)
        if pos == 0:
            q.appendleft(a)
        else:
            q[pos-1] = a

    return len(q)


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

Submission status: Accepted

Solution code:
import bisect;n,a,l=int(input()),[-int(input())],1
for i in range(n-1):
  b=-int(input())
  if a[-1]>b:a[bisect.bisect_right(a,b)]=b
  else:a.append(b);l+=1
print(l)

Submission status: Accepted

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

print(len(A))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect
N = int(input())
arr = [int(input()) for i in range(N)]
dp = [-1 for _ in range(N)]
for i in arr:
    dp[bisect.bisect_left(dp, i) - 1] = i
print(sum([i >= 0 for i in dp]))

Submission status: Accepted

Solution code:
import bisect

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

print(sum([i >= 0 for i in dp]))