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: Wrong Answer

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

color = [float("inf")]
for i in a:
    if i <= min(color):
        color.append(i)
print(len(color) - 1)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N = int(input())

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

color = 1
for i in range(1,N):
   if(A[i]<=A[i-1]):
      color += 1
   else:
      continue

print(color)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 5 + 10)
import bisect

import math



def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    ans = 0
    now_list = [data[0]]

    for i in range(1, num):
        if data[i] <= now_list[0]:
            now_list = [data[i]] + now_list
        else:
            ind = bisect.bisect_right(now_list, data[i])
            now_list[ind - 1] = data[i]

        # print(now_list)



    print(len(now_list))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

counter = 0
tmp_min = 10 ** 10
for i in range(n):
    if a[i] <= tmp_min:
        counter += 1
        tmp_min = a[i]

print(counter)

Submission status: Wrong Answer

Solution code:
a=[int(input())for i in[0]*int(input())]
print(1+len([0for i in a[1:]if i<=a[0]]))

Submission status: Wrong Answer

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")
    ans = 0
    for i in range(n):
        if a[i] <= mi:
            mi = a[i]
            ans += 1
    print(ans)
    return

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

    return

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

Submission status: Wrong Answer

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

q = 10**9
p = A[0]
ans = 1
flag = 0
for i in range(1,N):
    if p >= A[i]:
        if q >= A[i]:
            ans += 1
        q = p
        flag = 1
    else:
        if q < A[i] and flag:
            q = p
            flag = 0
    p = A[i]

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())

arr = []

for i in range(N):
    a = int(input())
    if len(arr) == 0:
        arr.append(a)
        continue

    index = bisect.bisect_left(arr, a)

    if arr[index - 1] < a:
        arr[index - 1] = a
    else:
        arr.append(a)

print(len(arr))

Submission status: Wrong Answer

Solution code:
#

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

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

    lsbs = deque()
    for a in al:
        pos = bisect.bisect_left(lsbs, a)
        if pos == 0:
            lsbs.appendleft(a)
        else:
            lsbs[min(pos, len(lsbs)-1)] = a
    print(len(lsbs))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
a=[int(input())for i in[0]*int(input())]
print(1+len([0for i in a[1:]if i>a[0]]))

Submission status: Wrong Answer

Solution code:
import numpy as np
import math

N = int(input())

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

color = 1
for i in range(1,N-1):
   if(A[i]>A[i+1]):
      color += 1
   else:
      continue

print(color)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ans = 1
t = []
t.append(A[0])

print(t[-1])
for i in range(1,N):
	if t[0] >= A[i]:
		ans += 1
		t.append(A[i])
		t = sorted(t)
	elif t[-1] < A[i]:
		t[-1] = A[i]
	else:
		for j in range(1, len(t)):
			if t[j] >= A[i]:
				t[j-1] = A[i]
print(ans)

Submission status: Wrong Answer

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

c = 1
mi = a.pop(0)
for ai in a:
  if ai <= mi:
    mi = ai
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:
N = int(input())

color = [0] * N

for _ in range(N):
    a = int(input())
    b = False
    for i, c in enumerate(color):
        if a > c:
            color[i] = a
            b = True
            break

ans = 0

for n in color:
    if n != 0:
        ans += 1
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A =  []
for i in range(N):
    A.append(int(input()))
    
count = 1
tmp = A[0]
for i in range(1,N):
    if tmp >= A[i]:
        count = count+1
        tmp = A[i]

print(count)

Submission status: Wrong Answer

Solution code:
N = input()
N = int(N)
S = [int(input()) for _ in range(N)]
result = 0

for i in range(N):
    if S[i] >= 0:
        result += 1
        hoge = S[i]
        for j in range(i+1,N):
            if S[j] >= hoge:
                hoge = S[j]
                S[j] = -1 
print(result)

Submission status: Wrong Answer

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

c = 1
mi = a.pop(0)
for ai in a:
  if ai < mi:
    mi = ai
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:
n = int(input())
small = 1000000000000
cnt = 0
for i in range(n):
    a = int(input())
    if a <= small:
        cnt += 1
        small = a
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]*N
num = 0
now = 10**9+1
for i in range(N):
    t = int(input())
    if t <= now:
        num += 1
        now = t
print(num)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[int(input()) for _ in range(n)]+[-1]
ans=0
for i in range(n):
  if arr[i]>=arr[i+1]:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
nums = [int(input()) for i in range(n)]
revNums = nums[::-1]
maxNum = -1
count = 0
for i in range(n):
    if maxNum <= revNums[i]:
        maxNum = revNums[i]
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict

n = int(input())

used = defaultdict(int)
a0 = int(input())
tank = [a0]
plus = [-a0]
used[a0] = 1

for i in range(1,n):
    a = int(input())
    while True:
        if used[tank[0]] > 0:
            break
        else:
            heapq.heappop(tank)
    #塗り替え
    if tank[0] < a:
        nu = - heapq.heappop(plus)
        used[nu] -= 1
        heapq.heappush(tank,a)
        used[a] += 1
        heapq.heappush(plus,-a)
    else:
        heapq.heappush(tank,a)
        used[a] += 1
        heapq.heappush(plus,-a)
res = 0
for e in tank:
    if used[e] > 0:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
B = [A[0]]
ans = 1
for a in A[1:]:
    b = bisect.bisect_left(B,a)
    if b==ans:
        B[ans-1] = a
    elif B[b] == a:
        bisect.insort_left(B,a)
        ans+=1
    else:
        if b==0:
            bisect.insort_left(B,a)
            ans+=1
        else:
            B[b-1] = a
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import copy
import numpy as np

n = int(input())
i = 0
prev = 0
count = 0
while i < n:
  x = int(input())
  if prev >= x:
    count += 1
  prev = x
  i += 1
  
print(count)

Submission status: Wrong Answer

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

min = a_list[0]
count = 1
for i in range(1,n):
    if a_list[i] <= min:
        min = a_list[i]
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = [int(input())]
for i in range(n-1):
    now = int(input())
    for q in range(len(ans)):
        if ans[q] < now:
            ans[q] = now
            break
        if q == len(ans)-1:
            ans.append(q)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect
def LIS(seq):
    dp = [seq[0]]
    for e in seq:
        if e > dp[len(dp)-1]:
            dp.append(e)
        else:
            dp[bisect.bisect_left(dp, e)] = e
    return dp

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

col_num = 0
while seq:
    dp = LIS(seq)
    ind = 0
    _seq = []
    for s in seq:
        if ind < len(dp) and s == dp[ind]:
            ind += 1
        else:
            _seq.append(s)
    seq = _seq
    col_num += 1
    
print(col_num)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import deque

def main():
    inf=float("inf")
    sm=1
    n=int(input())
    alst=[inf]*n
    work=[inf]*n
    index_list=[inf]*n
    for i in range(n):
        a=int(input())
        alst[i]=a
        j=bisect_left(work,a)
        work[j]=a
        index_list[j]=i
    alst=[x for i,x in enumerate(alst) if not i in index_list]

    while alst:
        sm+=1
        n=len(alst)
        work=[inf]*n
        index_list=[inf]*n
        for i in range(n):
            a=alst[i]
            j=bisect_left(work,a)
            work[j]=a
            index_list[j]=i
        alst=[x for i,x in enumerate(alst) if not i in index_list]
    print(sm)

main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(input())]
for i in range(N-1):
  a=int(input())
  if a<=min(A):
    A.append(a)
  else:
    for j,ls in enumerate(A[::-1]):
      if ls>=a:
        A[-j]=a
        break
    else:
      A[0]=a
print(len(A))

Submission status: Time Limit Exceeded

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

LIS = []  # LISの中身は、LISの最小の数字を保持する
LIS.append(a[0])
for i in range(1, n):
    idx = bisect_left(LIS, a[i])
    if idx == 0:
        LIS = [a[i]] + LIS
    else:
        LIS[idx-1] = a[i]
print(len(LIS))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
seq = [int(input()) for _ in [0]*N]

ans = 0
while True:
    ans += 1
    LIS = [seq[0]]
    seq_n = []
    for i in range(len(seq)):
        if seq[i] > LIS[-1]:
            LIS.append(seq[i])
        else:
            seq_n.append(LIS[bisect.bisect_left(LIS, seq[i])])
            LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
    seq_n.pop(0)
    if len(seq_n)==0:
        break
    else:
        seq = seq_n
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[-1]*(n+1)

for i in range(n):
  a=int(input())
  j=0
  while a<=l[j]:
    j=j+1
  l[j]=a

cnt=0
while l[cnt]!=-1:
  cnt+=1
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N= int(input())
dp = [-1]*N
cnt =0
for i in range(N):
    a = int(input())
    idx = bisect.bisect_left(dp[N-i-1:],a)
    dp[(N-i-1)+idx-1]=a
print(len(dp[bisect.bisect_left(dp,0):]))

Submission status: Time Limit Exceeded

Solution code:
N= int(input())
dp = [-1]*N
cnt =0
for _ in range(N):
    a = int(input())
    for i in range(N):
        if dp[i]<a:
            dp[i]=a
            cnt = max(cnt,i)
            break
print(cnt+1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
ans = 1
for i in range(1, n):
    if min(a[:i]) >= a[i]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N):
    for j in range(N):
        if A[i] > dp[j]:
            dp[j] = A[i]
            ans = max(ans, j+1)
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
WIDE = 10**5 + 10

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

dp = [[-1] for _ in range(WIDE)]

for i in range(N):
    for j in range(len(dp)):
        if dp[j][-1] < A[i]:
            dp[j].append(A[i])
            break

count = 0
for i in range(WIDE):
    if len(dp[i]) >= 2:
        count += 1
    if len(dp[i]) == 1:
        break       

print(count)

Submission status: Time Limit Exceeded

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

N = int(input())
A = [int(input()) for _ in range(N)]
INF = 10**18
arr = []
for a in A:
    l, r = -1, len(arr)
    while (r-l) > 1:
        mid = (r+l)//2
        if arr[mid] < a:
            l = mid
        else:
            r = mid
    if l == -1:
        arr = [a]+arr
    else:
        arr[l] = a
print(len(arr))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)
B = [A[0]]
for i in range(1, N):
    j = 0
    while j<len(B):
        if A[i] > B[j]:
            B[j] = A[i]
            break
        j+=1
    else:
        B.append(A[i])

print(len(B))

Submission status: Time Limit Exceeded

Solution code:
# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys
import bisect

N = int(input())
now = int(sys.stdin.readline().strip())
ans = [now]

for n in range(N - 1):
    now = int(sys.stdin.readline().strip())

    if now > ans[0]:
        ans[0] = now
    elif ans[-1] >= now:
        ans.append(now)
    else:
        # 2部探査で行進位置を探る
        left = 0  # 挿入不可能
        right = len(ans) - 1  # 挿入可能

        while right - left > 1:
            mid = (right - left) // 2
            if ans[mid] > now:
                right = mid
            else:
                left = mid

        ans[right] = now

print(len(ans))

    # if ans:  # 最初の入力以外であり、すでに追加対象のリストが存在する
    #     if ans[0][-1] < now:
    #         ans[0].append(now)
    #     elif ans[-1][-1] >= now:
    #         appending = [now]
    #         ans.append(appending)
    #     else:
    #         # 二分探索で追加するリストの位置を特定する
    #         left = 0   # 追加できない  ans[left][-1] > now
    #         right = len(ans) - 1  # ans[right][-1] < now
    #
    #         while right - left > 1:
    #             mid = (right - left) // 2
    #             if ans[mid][-1] < now:
    #                 right = mid
    #             else:
    #                 left = mid
    #         ans[right].append(now)
    # else:
    #     appending = [now]
    #     ans.append(appending)

    # for a in ans:
    #     if a[-1] < now:
    #         a.append(now)
    #         break
    # else:
    #     appending = [now]
    #     ans.append(appending)

# print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys

N = int(input())
ans = []

for n in range(N):
    now = int(sys.stdin.readline().strip())
    if ans:  # 最初の入力以外であり、すでに追加対象のリストが存在する
        if ans[0][-1] < now:
            ans[0].append(now)
        elif ans[-1][-1] >= now:
            appending = [now]
            ans.append(appending)
        else:
            # 二分探索で追加するリストの位置を特定する
            left = 0   # 追加できない
            right = len(ans) - 1

            while right - left > 1:
                mid = (right - left) // 2
                if ans[mid][-1] < now:
                    right = mid
                else:
                    left = mid
            ans[right].append(now)
    else:
        appending = [now]
        ans.append(appending)

    # for a in ans:
    #     if a[-1] < now:
    #         a.append(now)
    #         break
    # else:
    #     appending = [now]
    #     ans.append(appending)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys

N = int(input())
ans = []

for n in range(N):
    now = int(sys.stdin.readline().strip())
    for a in ans:
        if a[-1] < now:
            a.append(now)
            break
    else:
        appending = [now]
        ans.append(appending)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys

N = int(input())
ans = []

for n in range(N):
    now = int(input())
    for a in ans:
        if a[-1] < now:
            a.append(now)
            break
    else:
        appending = [now]
        ans.append(appending)

print(len(ans))

Submission status: Time Limit Exceeded

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

color=0
while A:#for i in range(10):
  color+=1
  LCS=[]
  inds=[]
  for i in range(len(A)):
    sny=bisect.bisect_left(LCS,A[i])
    if sny==len(LCS):
      LCS.append(A[i])
      if sny-1>=0:
        inds.append(i)
      else:
        inds.append(i)
    #inds[sny][-1]=i
    LCS[sny]=A[i]
  #最長増加部分列を取り除く
  ind=0
  out=[]
  for i in range(len(A)-1,-1,-1):
    #print(inds[-1][-ind-1])
    if i==inds[-ind-1]:
      ind+=1
      A.pop(i)
      #print(len(A))
      if ind >= len(LCS):
        break
print(color)

Submission status: Time Limit Exceeded

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

color=0
while A:#for i in range(10):
  color+=1
  LCS=[]
  inds=[]
  for i in range(len(A)):
    sny=bisect.bisect_left(LCS,A[i])
    if sny==len(LCS):
      LCS.append(A[i])
      if sny-1>=0:
        inds.append(inds[sny-1][:]+[i])
      else:
        inds.append([i])
    inds[sny][-1]=i
    LCS[sny]=A[i]
  #最長増加部分列を取り除く
  ind=0
  out=[]
  for i in range(len(A)-1,-1,-1):
    #print(inds[-1][-ind-1])
    if i==inds[-1][-ind-1]:
      ind+=1
      A.pop(i)
      #print(len(A))
      if ind >= len(LCS):
        break
print(color)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
minList=[]
for i in range(N):
  if i==0:
    a=int(input())
    minList.append(a)
  else:
    a=int(input())
    MAX=-1
    argmax=-1
    for j in range(len(minList)):
      if minList[j]>=MAX and minList[j]<a:
        argmax=j
        MAX=minList[j]
    if MAX==-1:
      minList.append(a)
    else:
      minList[argmax] = a

print(len(minList))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
minList=[]
for i in range(N):
  if i==0:
    a=int(input())
    minList.append([a])
  else:
    a=int(input())
    MAX=-1
    argmax=-1
    for j in range(len(minList)):
      if minList[j][-1]>=MAX and minList[j][-1]<a:
        argmax=j
        MAX=minList[j][-1]
    if MAX==-1:
      minList.append([a])
    else:
      minList[argmax].append(a)

print(len(minList))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect

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

def loopa(a):

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


#    dq2.sort() 
#    for i in range(len(dq2)-1,-1,-1):
#        del a[dq2[i]]
#    print(dq2)
    a=[a[i] for i in range(n) if not (i in dq2)]
    return a

icnt=0
while len(a)>0:
#    if icnt>10:break
    a=loopa(a)        
    icnt+=1

print(icnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import queue
INF=10**18
n=int(input())
a=queue.Queue()
for _ in range(n):
  a.put(int(input()))
cnt=0
while a.qsize():
  dp=[]
  for i in range(a.qsize()):
    i=a.get()
    if bisect.bisect_left(dp,i)==len(dp):
      dp.append(i)
    else:
      a.put(bisect.bisect_left(dp,i))
      dp[bisect.bisect_left(dp,i)]=i
  cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

ans = 0
while len(A) > 0:
  dp = []
  l = len(A)
  for _ in range(l):
    a = A.popleft()
    if len(dp)==0:
      dp.append(a)
    elif a > dp[-1]:
      dp.append(a)
    else:
      pos = bisect.bisect_left(dp, a)
      A.append(dp[pos])
      dp[pos] = a
  ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# YouTube解説の方法（deque使わない）
from bisect import bisect_left
import sys
input = sys.stdin.readline

def bisect_right_reverse(L, target):
    return len(L) - bisect_left(L[::-1], target)

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

L = []
for i in range(N):
    k = bisect_right_reverse(L, A[i])
    if k == len(L):
        L.append(A[i])
    else:
        L[k] = A[i]

print(len(L))

Submission status: Time Limit Exceeded

Solution code:
# YouTube解説の方法（deque使わない）
from bisect import bisect_left

def bisect_right_reverse(L, target):
    return len(L) - bisect_left(L[::-1], target)

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

L = []
for i in range(N):
    k = bisect_right_reverse(L, A[i])
    if k == len(L):
        L.append(A[i])
    else:
        L[k] = A[i]

print(len(L))

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 4 + 7

N = int(input())

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

d = []
for a in A:
    l = -1
    r = len(d)
    while r - l > 1:
        m = l + (r - l) // 2
        if d[m] >= a:
            r = m
        else:
            l = m
    if r == 0:
        d = [a] + d
    else:
        d[r - 1] = a
print(len(d))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import deque

n = int(input())
ans = []
ans.append(int(input()))

for i in range(n-1):
  
  temp = int(input())
  #print("ans " +  str(ans) + " temp " + str(temp))
  if temp <= ans[0]:
    d = deque(ans)
    d.appendleft(temp)
    ans = list(d)
  else:
    loc = bisect_left(ans, temp)
    ans[loc-1]=temp
#print(ans)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
N = int(input())
A = [int(input()) for _ in range(N)][::-1]
res = [A[0]]
for a in A[1:]:
    idx = bisect_right(res, a)
    if idx == len(res):
        res.append(a)
    else:
        if res[idx] == a:
            res.append(a)
        else:
            res[idx] = a
        res.sort()
print(len(res))

Submission status: Time Limit Exceeded

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

color_num = [a[0]]
cnt = 1
for i in range(1, n):
    if a[i] <= color_num[0]:
        color_num = [a[i]] + color_num
        cnt += 1
    else:
        temp = bisect.bisect_left(color_num, a[i])
        color_num[temp - 1] = a[i]

print(cnt)

Submission status: Time Limit Exceeded

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

color_num = [a[0]]
cnt = 1
for i in range(1, n):
    temp = bisect.bisect_left(color_num, a[i])
    if cnt == temp:
        color_num[temp - 1] = a[i]
    elif temp == 0:
        color_num = [a[i]] + color_num
        cnt += 1
    else:
        color_num[temp - 1] = a[i]

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    n = int(input())
    seq = [int(input()) for _ in range(n)]

    # リストseqからLISの長さを出す

    import bisect
    
    def main():
        cnt=0
        while len(seq)>0:

            LIS = [seq[0]]
            for i in range(len(seq)):
                if seq[i] > LIS[-1]:
                    LIS.append(seq[i])
                else:
                    LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
            cnt+=1
            
            for i in LIS:
                seq.remove(i)
        return cnt
    print(main())
    




resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop


def read():
    N = int(input().strip())
    A = [int(input().strip()) for _ in range(N)]
    return N, A


class SegmentTree():
    
    def __init__(self, size, init_value=10**8):
        """初期化"""
        self.size = size
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [init_value] * treesize
        st_idx = [i for i in range(treesize)]
        self.st = st
        self.st_idx = st_idx
        self.offset = len(st) // 2

    @classmethod
    def from_array(cls, a, init_value=10**8):
        st = cls(len(a), init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        k = self.offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            if self.st[k * 2] <= self.st[k * 2 + 1]:
                self.st[k] = self.st[k * 2]
                self.st_idx[k] = self.st_idx[k * 2]
            else:
                self.st[k] = self.st[k * 2 + 1]
                self.st_idx[k] = self.st_idx[k * 2 + 1]
            k >>= 1

    def _smallest(self, a, b):
        """区間[a, b) の最小値を検索し、(index, value)の組を返す
        """
        a += self.offset
        b += self.offset - 1
        s = self.init_value
        idx = -1
        while a < b:
            if a & 1:
                if self.st[a] <= s:
                    s = self.st[a]
                    idx = self.st_idx[a]
                a += 1
            a >>= 1
            if not b & 1:
                if self.st[b] <= s:
                    s = self.st[b]
                    idx = self.st_idx[b]
                b -= 1
            b >>= 1
        if a == b:
            if self.st[a] <= s:
                s = self.st[a]
                idx = self.st_idx[a]
        return idx - self.offset, s

    def smallest(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._smallest(a, b)
    
    def _find_le(self, value, k=1):
        """value以下の最大の値を検索し、(index, value)の組を返す
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if value < self.st[k]:
            return (len(self.st), -self.init_value)
        elif value == self.st[k] or k >= self.offset:
            return (self.st_idx[k], self.st[k])
        else:
            li, lv = self._find_le(value, k * 2)
            ri, rv = self._find_le(value, k * 2 + 1)
            mi = li if lv >= rv else ri
            mv = lv if lv >= rv else rv
            if mi < len(self.st):
                return (mi, mv)
            else:
                return (len(self.st), -self.init_value)
    
    def find_le(self, value):
        """value以下の最大値を検索し、(index, value)の組を1つ返す
        見つからない場合は-1を返す
        """
        i, v = self._find_le(value, k=1)
        if i == len(self.st):
            return (-1, self.init_value)
        else:
            return (i - self.offset, v)


def solve(N, A, INF=10**9+1):
    st = SegmentTree(N)
    l = 0
    for a in A[::-1]:
        k, v = st.find_le(-a-1)  # 以下を未満にするため-1
        if k == -1:
            st.update(l, -a)
            l += 1
        else:
            st.update(k, -a)
    return l


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))