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())
x=[int(input())]
for i in range(n-1):
  a=int(input())
  if x[-1]>=a:
    x+=[a]
  else:
    low=0
    high=len(x)-1
    mid=(high+low)//2
    while high-low>1:
      if x[mid]<a:
        high=mid
      else:
        low=mid
      mid=(high+low)//2
    if x[mid]<a:
      x[mid]=a
    else:
      x[high]=a
print(len(x))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = [int(input()) for _ in range(n)]
r = [-1] * n
for a in a:
    i = bisect.bisect_left(r, a)
    r[i - 1] = a
print(len(r) - r.count(-1))

Submission status: Accepted

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

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

s = deque([a[0]])

from bisect import bisect_left

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

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

Submission status: Accepted

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

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

dp = [10**10] * N

for a in A:
    a = -a
    dp[bisect_right(dp, a)] = a

ans = N - dp.count(10**10)
print(ans)

Submission status: Accepted

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

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)
    a = [-i for i in a]
    dp = [float("inf")]*n
    for i in a:
        j = bisect.bisect_right(dp,i)
        dp[j] = i
    print(n-dp.count(float("inf")))
    return

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

Submission status: Accepted

Solution code:
import bisect
from collections import deque

n = int(input())
A = []
dq_A = deque(A)
count = 0
for _ in range(n):
    a = int(input())
    if len(dq_A) == 0:
        dq_A.appendleft(a)
        count += 1
        continue
    i = bisect.bisect_left(dq_A, a)
    if i == 0:
        dq_A.appendleft(a)
        count += 1
    else:
        dq_A[i-1] = a

ans = count
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def lower_bound(al, key):
    def isOk(a):
        return a<key

    ng = len(al)
    ok = -1

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

n = int(input())
al = [int(input()) for _ in range(n)]
c = deque()

for a in al:
    if len(c) == 0:
        c.append(a)
        continue

    idx = lower_bound(c,a)
    if idx==-1:
        c.appendleft(a)
    else:
        c[idx] = a

print(len(c))

Submission status: Accepted

Solution code:
# E
n = int(input())
from collections import deque
import bisect
first = int(input())
a = [first]
a = deque(a) # でキュー化

for i in range(n-1):
    num = int(input())
    
    if num <= a[0]:
        a.appendleft(num)
    else:
        ind = bisect.bisect_left(a, num)
        ind-=1
        a[ind]=num
print(len(a))

Submission status: Accepted

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

import bisect

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

Q = []
x = 0

for a in A:
    idx = bisect.bisect_right(Q, -a)

    if idx >= len(Q):
        x += 1
        Q.append(-a)
    else:
        Q[idx] = -a

print(x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

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

dq = deque()
for e in a:
    idx = bisect_left(dq, e)
    if idx == 0:
        dq.appendleft(e)
    else:
        dq[idx-1] = e

ans = len(dq)
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)]
ans = deque([a[0]])
for a_i in a[1:]:
    if ans[0] < a_i:
        i = bisect_left(ans, a_i)
        ans[i-1] = a_i
    else:
        ans.appendleft(a_i)

print(len(ans))

Submission status: Accepted

Solution code:
from bisect import bisect_right
n = int(input())
ans = 1
data = [-int(input())]
for i in range(n-1):
    x = -int(input())
    j = bisect_right(data,x)
    if j == ans:
        data.append(x)
        ans += 1
    else:
        data[j] = x
print(ans)

Submission status: Accepted

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

import bisect
from collections import deque
q = deque()
q.append(a[0])

for num in a[1:]:
    if num <= q[0]:
        q.appendleft(num)
    else:
        ind = bisect.bisect_left(q,num)
        ind-=1
        q[ind]=num

print(len(q))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc134/tasks/abc134_e
import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left
from array import array


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


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

    # def __repr__(self):
    #     return f'BST:{self.bst}'

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        # idx = self.bisect_left(x)
        # self.bst.insert(idx,x)
        insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

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

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    # すべてより小さかったら、新しく追加
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        # bstのなかで、aより小さく且つ一番大きい要素をaに書き換えていく
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc134/tasks/abc134_e
import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left
from collections import deque
from array import array


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = array('l',sorted(ls))  # insertをO(1)にするためにlistの代わりにdequeを用います

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        idx = self.bisect_left(x)
        self.bst.insert(idx, x)
        # insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

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

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    # すべてより小さかったら、新しく追加
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        # bstのなかで、aより小さく且つ一番大きい要素をaに書き換えていく
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))

Submission status: Accepted

Solution code:
import bisect

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

p = [A[0]]
for i in A[1:]:
    if p[-1] <= i:
        p.append(i)
    else:
        p[bisect.bisect_right(p,i)] = i
print (len(p))

Submission status: Accepted

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

    color=[]
    for i in range(n-1,-1,-1):
        num=a[i]
        idx=bisect_right(color,num)
        if idx==len(color):
            color.append(num)
        else:
            color[idx]=num
    
    print(len(color))    
if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect
import collections

N=int(input())

line=collections.deque()

for _ in range(N):
    A=int(input())
    index=bisect.bisect_left(line,A)
    if index==0:
        line.appendleft(A)
    else:
        line[index-1]=A
    #print(line)
    
    #print(line)

print(len(line))

Submission status: Accepted

Solution code:
def JOI14_B():
    N = I()
    A = [I()for _ in range(N)]
    A.extend(A)
    dp = [[0]*(N*2+1) for _ in range(N*2+1)]

    for j in range(N):
        for i in range(N*2-j):
            if (N-j)%2==1:
                dp[i][i+j] = max(dp[i+1][i+j]+A[i],dp[i][i+j-1]+A[i+j])
            else:
                if A[i]>A[i+j]:
                    dp[i][i+j] = dp[i+1][i+j]
                else:
                    dp[i][i+j] = dp[i][i+j-1]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i+N-1])
    print(ans)
    #print(dp)
    return

def square869120Contest1_G():
    def held_karp(dists,TL):
        # Copyright (c) 2016 Carl Ekerot
        """
        Implementation of Held-Karp, an algorithm that solves the Traveling
        Salesman Problem using dynamic programming with memoization.
        Parameters:
            dists: distance matrix
        Returns:
            A tuple, (cost, path).
        """
        n = len(dists)

        # Maps each subset of the nodes to the cost to reach that subset, as well
        # as what node it passed before reaching this subset.
        # Node subsets are represented as set bits.
        C = {}
        dp = defaultdict(int)

        # Set transition cost from initial state
        for k in range(1, n):
            C[(1 << k, k)] = (dists[0][k], 0)
            dp[(1 << k, k)] = 1

        # Iterate subsets of increasing length and store intermediate results
        # in classic dynamic programming manner
        for subset_size in range(2, n):
            for subset in itertools.combinations(range(1, n), subset_size):
                # Set bits for all nodes in this subset
                bits = 0
                for bit in subset:
                    bits |= 1 << bit
                shortest_length = inf
                # Find the lowest cost to get to this subset
                for k in subset:
                    prev = bits & ~(1 << k)

                    res = []
                    for m in subset:
                        if not (prev, m) in C:
                            continue
                        if m == 0 or m == k:
                            continue
                        if C[(prev, m)][0] + dists[m][k]>TL[m][k]:
                            continue
                        res.append((C[(prev, m)][0] + dists[m][k], m))
                        if shortest_length>C[(prev, m)][0] + dists[m][k]:
                            shortest_length = C[(prev, m)][0] + dists[m][k]
                    if not res:
                        continue
                    C[(bits, k)] = min(res)
                    for d,m in res:
                        if shortest_length!=d:
                            continue
                        dp[(bits, k)] += dp[(prev,m)]

        # We're interested in all bits but the least significant (the start state)
        bits = (2 ** n - 1) - 1

        # Calculate optimal cost
        res = []
        shortest_length = inf
        for k in range(1, n):
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            res.append((C[(bits, k)][0] + dists[k][0], k))
            if shortest_length > C[(bits, k)][0] + dists[k][0]:
                shortest_length = C[(bits, k)][0] + dists[k][0]
        if not res:
            return False
        opt, parent = min(res)
        way = 0
        for d, k in res:
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            if shortest_length < d:
                continue
            way += dp[(bits,k)]

        # Backtrack to find full path
        path = []
        for i in range(n - 1):
            path.append(parent)
            new_bits = bits & ~(1 << parent)
            _, parent = C[(bits, parent)]
            bits = new_bits

        # Add implicit start state
        path.append(0)

        return shortest_length, list(reversed(path)), way

    N, M = LI()
    dist = [[inf]*N for _ in range(N)]
    TL = [[0]*N for _ in range(N)]
    for _ in range(M):
        s, t, d, time = LI()
        s -= 1; t -= 1
        dist[s][t] = dist[t][s] = d
        TL[s][t] = TL[t][s] = time
    ans = held_karp(dist,TL)
    if (not ans) or ans[2]==0:
        print("IMPOSSIBLE")
        return
    print(ans[0],ans[2])
    return

def JOI13_D():
    def solve(yday,leader,next):
        a = [0]*3
        for i in range(3):
            if next&(1<<i)==(1<<i):
                a[i] = 1
        rep = 0
        if a[leader]==0:
            return rep
        for i in range(3):
            if yday&(1<<i)==(1<<i):
                if a[i]==1:
                    rep = 1
        return rep
    N = I()
    S = SI()
    member = {"J":0,"O":1,"I":2}
    dp = [[0]*8 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(N):
        leader = member[S[i]]
        for j in range(8):
            for k in range(8):
                dp[i+1][j] += (dp[i][k]*solve(k,leader,j))
    ans = sum(dp[-1])%10007
    #print(dp)
    print(ans)
    return

def JOI16_D():
    N, M = LI()
    A = [(I()-1)for _ in range(N)]
    imos = [[0] * (N + 1) for _ in range(M)]
    for i in range(M):
        for j in range(N):
            imos[i][j + 1] += imos[i][j] + (A[j] != i)
    cnt = Counter(A)
    dp = [10 ** 9] * (1 << M)
    num = [None] * (1 << M)
    dp[0] = 0
    num[0] = 0
    for b in range(1 << M):
        for i in range(M):
            if b & (1 << i):
                continue
            nb = b | (1 << i)
            if num[nb] is None:
                num[nb] = num[b] + cnt[i]
            l = num[b]
            r = l + cnt[i]
            d = imos[i][r] - imos[i][l]
            dp[nb] = min(dp[nb], dp[b] + d)

    print(dp[-1])
    return

def ABC6_D():
    N = I()
    C = [I() for _ in range(N)]
    LIS = [C[0]]
    for i in range(N):
        if C[i] > LIS[-1]:
            LIS.append(C[i])
        else:
            LIS[bisect.bisect_left(LIS, C[i])] = C[i]
    print(N - len(LIS))
    return

def ABC134_E():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    L = 1
    for i in range(1,N):
        cur = bisect.bisect_left(que,A[i])
        #print(que,cur,L)
        if cur==0:
            que.appendleft(A[i])
            L += 1
        else:
            que[cur-1] = A[i]

    #print(que)
    ans = len(que)
    print(ans)

    return

def JOI7_F():
    n, k = LI()
    for _ in range(k):
        A = LI()

    return

def square869120Contest1_E():
    N, Q = LI()
    A = LI()
    C = LI()
    C.append(1)
    L = [0]*N
    for i in range(1,N):
        L[i] = pow(A[i-1],A[i],mod) + L[i-1]
    #print(L)
    ans = 0
    now = 0
    for i in range(Q+1):
        next = C[i]-1
        cur = abs(L[next]-L[now])
        ans += cur
        ans %= mod
        now = next
        #print(ans)
    print(ans)
    return

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

if __name__ == '__main__':
    ABC134_E()
"""

"""

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
a = []
for _ in range(N): a.append(int(input()))
lis = [float("inf") for _ in range(N)]
reva = a[: : -1]

for i in range(N):
  j = br(lis, reva[i])
  lis[j] = reva[i]

res = N
for i in range(N):
  if lis[i] == float("inf"):
    res = i
    break
print(res)

Submission status: Accepted

Solution code:
from collections import deque
import bisect
import sys

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

col = [A.pop()]
col = deque(col)

while A:
    a = A.pop()
    if a <= col[0]:
        col.appendleft(a)
    else:
        x = bisect.bisect_left(col, a)
        col[x - 1] = a

ans = len(col)
print(ans)

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]"):
    deq = deque([-1])

    for i in range(N):
        index = bisect_left(deq,A[i])
        if index == 0:
            deq.appendleft(A[i])
        else:
            deq[index-1] = A[i]
    print(len(deq))
    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 bisect import bisect_right

def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD = 10 ** 9 + 7

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

# 広義単調減少列の長さの最大値を求めれば良い = Aを逆順に見ればLISと同値
# dp[i] := 長さがi以下の部分列で作られる広義単調減少列の最後の要素の最大値
dp = [-1]  # A[i] >= 0 なのでそれ以下の値を設定し、数列の単調性を保つ
for a in reversed(A):
    if dp[-1] <= a:
        dp.append(a)
    else:
        idx = bisect_right(dp, a)  # "広義"のため、同じ値が複数の場合は最も右のもの(right)
        dp[idx] = a
print(len(dp) - 1)

Submission status: Accepted

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

sys.setrecursionlimit(10000)

N = int(input())
import bisect

L = [1]
ans = 1
for i in range(N):
    A = int(input())
    res = bisect.bisect_right(L, -A)
    if res != ans:
        L[res] = -A
    else:
        L.append(-A)
        ans += 1
print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    use = deque([10**9+1])
    for _ in range(N):
        num = int(input())
        index = bisect.bisect_left(use,num)
        if index == 0:
            use.appendleft(num)
        else:
            use[index-1] = num
    
    print(len(use)-1)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N = int(input())
    use = deque([int(input())])
    for _ in range(N-1):
        num = int(input())
        index = bisect.bisect_left(use,num)
        if index == 0:
            use.appendleft(num)
        else:
            use[index-1] = num
    
    print(len(use))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect
def main():
    N,*A=map(int, open(0).read().split())
    B=[]
    for a in A:
        x=bisect(B,-a)
        if x>=len(B):
            B.append(-a)
        else:
            B[x]=-a
    print(len(B))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# LDS最長減少部分列
# 解説放送
# dilworthの定理
# パスを通してどの2点間も移動できないような点集合の点の個数 = 最小パス被覆
# 移動できないような点は
# 右側（大きい値側）から見て以上になっているような数列

from bisect import bisect_right

inf = 10 ** 9 + 1

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

t = [inf]
for x in reversed(a):
    if t[-1] <= x:
        t.append(x)
    else:
        insert_pos = bisect_right(t, x)
        t[insert_pos] = x

ret = len(t)

print(ret)

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([-1])
for x in a:
    insert_pos = bisect_left(q, x) - 1
    # bisect_left[0,len(lis)] == 以上の最小
    # 手前は未満の最大[-1,len(lis))
    if insert_pos == -1:
        q.appendleft(x)
    else:
        q[insert_pos] = x

ret = len(q)

print(ret)

# 最小パス被覆

Submission status: Accepted

Solution code:
#17:21
from collections import deque
import bisect
n = int(input())
now = deque()
for _ in range(n):
  tmp = int(input())
  b = bisect.bisect_left(now,tmp)
  if b != 0:
    now[b-1] = tmp
  else:
    now.appendleft(tmp)
print(len(now))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def main():
  n = I()
  a = [I() for _ in range(n)]
  dp = [inf]*n
  for i in range(n):
    r = br(dp,-a[i])
    dp[r] = -a[i]
  print(n-dp.count(inf))
  return

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque
N = int(input())
a = int(input())
ls = deque([a])
for i in range(N-1):
  c = int(input())
  ind = bisect_left(ls,c)
  if ind==0:
    ls.appendleft(c)
    continue
  ls[ind-1] = c
print(len(ls))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import bisect

N = int(input())
H = []
for _ in range(N):
    a = int(input())
    ind = bisect.bisect_right(H, -a)
    if ind == len(H):
        H.append(-a)
    else:
        H[ind] = -a
print(len(H))

Submission status: Accepted

Solution code:
import bisect

def main():
    n = int(input())
    buf = []
    a = [None] * n
    for i in range(n):
        a[i] = int(input())
    for i in reversed(a):
        index = bisect.bisect_right(buf, i)
        if index < len(buf) and buf[index] > i:
            buf[index] = i
        else:
            buf.append(i)
    print(len(buf))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right as bi_r

inf = float('inf')

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

def main():
    res = [inf] * n
    for a in A[::-1]:
        i = bi_r(res, a)
        res[i] = a

    for i in range(n):
        if res[i] == inf:
            return i
    return n
    
if __name__ == '__main__':
    ans = main()
    print(ans)

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

ans=1
data=deque([A[0]])
for i in range(1,N):
    a=A[i]
    b=bisect_left(data,a)
    if b==0:
        data.appendleft(a)
        ans+=1
    else:
        data[b-1]=a

print(ans)

Submission status: Accepted

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

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

d = []
for i in range(N):
    p = bisect.bisect_right(d, A[i])
    if p==len(d):
        d.append(A[i])
    else:
        d[p] = A[i]
ans = len(d)
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import deque
import bisect

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

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

Submission status: Accepted

Solution code:
import sys
import bisect

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

N = ir()
INF = 10 ** 10
dp = [INF] * N
# マイナスの値にしてLongest Increasing Sequence
for _ in range(N):
    a = 10 ** 9 - ir()
    i = bisect.bisect_right(dp, a)
    dp[i] = a

index = bisect.bisect_left(dp, INF)
print(index)
# 04

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

N = int(input())
d = deque([])
l = [int(input()) for _ in range(N)]

d.append(l[0])

for i in l[1:]:
    v = bisect_left(d, i)
    if v == 0:
        d.appendleft(i)
    else:
        d[v-1] = i

print(len(d))

Submission status: Accepted

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

stack = []

def bisect(li, i):
    if len(li)==0:
        li.append(i)
        return
    ok = len(li)
    ng = -1
    while abs(ok-ng)>1:
        tmp = (ok+ng)//2
        if li[tmp]<i:
            ok = tmp
        else:
            ng = tmp
    if ok < len(li):
        li[ok] = i
    else:
        li.append(i)

for i in a:
    bisect(stack, i)
print(len(stack))

Submission status: Accepted

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

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

print(len(B))