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: Time Limit Exceeded

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

N = int(input())
L = [int(input()) for v in range(N)]

ans = 0
nl = []
while True:
    a = L[0]
    for v in L[1:]:
        if a < v:
            a = v
        else:
            nl.append(v)
    L = nl
    nl = []
    
    ans += 1
    
    if L == []:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = []

for _ in range(N):
    A.append(int(input()))

color_num = 0

while A != []:
    base = A[0]
    A.pop(0)

    looking = 0

    while looking < len(A):
        if base < A[looking] :
            base = A[looking]
            A.pop(looking)
        else:
            looking += 1

    color_num += 1

print(color_num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = []

for _ in range(N):
    A.append(int(input()))

colored = [False] * N
goal = [True] * N

color_num = 0

while colored != goal:
    start = colored.index(False)
    base = A[start]
    colored[start] = True

    for i in range(start+1, N):
        if colored[i] == False:
            if base < A[i] :
                colored[i] = True
                base = A[i]

    color_num += 1

print(color_num)

Submission status: Time Limit Exceeded

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

ans = 0
while len(A) != 0:
    tmp = A[0]
    ans += 1
    del(A[0])
    for num in A[:]:
        if tmp < num:
            A.remove(num)
            tmp = num

print(ans)

Submission status: Time Limit Exceeded

Solution code:
c=int(input())
l=[int(input()) for _ in range(c)]
for i in range(len(l)):

    for j in range(len(l)):
        if i <j and l[i] < l[j]:
            c=c-1
print(abs(c))

Submission status: Time Limit Exceeded

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

ret = [a[0]]
for i in range(1, n):
  for j in range(len(ret)):
    if a[i] > ret[j]:
      ret[j] = a[i]
      break
  else:
    ret.append(a[i])
print(len(ret))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

print(len(t))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = input()
a = []
n = int(n)

for i in range(n):
    a.append(int(input()))

# それぞれの色の最大値を入れる筒のリスト
t = []

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

print(len(t))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())

tops = []

for i in range(N):
    a = int(input())
    # 二分探索
    p = bisect.bisect_left(tops, a)
    
    if p == 0:
        bisect.insort_left(tops, a)
    else:    
        tops[p-1] = a
        
print(len(tops))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())

tops = []

for i in range(N):
    a = int(input())
    # 二分探索
    # aより小さい値の中で最大値の添え字 + 1
    p = bisect.bisect_left(tops, a)
    
    if p == 0:
        bisect.insort_left(tops, a)
    else:    
        tops[p-1] = a
        
print(len(tops))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
i=0
s=[]
while i!=n:
    s.append(int(input()))
    i+=1
i=0
ans=[-1]
j=0
f=0
p=0
while i!=n:
    while j!=len(ans):
        if ans[j]<s[i]:
            ans[j]=s[i]
            f=1
            break

        j+=1
    if f==0:
        ans.insert(0, s[i])

    f=0
    j=0
    i+=1
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N = int(input())
A = list(int(input()) for _ in range(N))
INF = 10 ** 9 + 1
V = [False for i in range(N)]
nv = 0
cnt = 0
while nv < N:
    dp = [INF]
    for i, a in enumerate(A):
        if V[i]:
            continue
        if a > dp[-1]:
            dp.append(a)
        else:
            j = bisect_left(dp, a)
            dp[j] = a
    nv += len(dp)
    dp.append(INF)
    m = len(dp)
    for i in range(N-1, -1, -1):
        if V[i]:
            continue
        if dp[m-1] <= A[i] < dp[m]:
            V[i] = True
            m -= 1
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
import math
mod = 10**9 + 7
def I(): return int(input())
def II(): return map(int, input().split())
def L(): return list(map(int, input().split()))
def TWO(M):
  L=[0]*M
  R=[0]*M
  for i in range(M):
    L[i],R[i] = II()
  return L, R

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

check = [0]*N
counter = 0
all_counter = 0
while 1:
  temp = -1
  for i in range(N):
    if check[i]==0 and temp<A[i]:
      check[i]=1
      temp = A[i]
      all_counter += 1
  counter += 1
  if all_counter==N:
    break
  
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
a = []
for i in range(N):
        x = int(input())
        a.append(x)
c = [0 for i in range(N)]
color = 0
if a == sorted(a, reverse=True):
        print(N)
        sys.exit()
for i in range(N-1,-1,-1):
        if sum(c) == N:
                #print("break:{}".format(i))
                break
        if c[i]: continue
        color += 1
        #print(color)
        x = a[i]
        c[i] = 1
        for j in range(i-1,-1,-1):
                if c[j]: continue
                if x > a[j]:
                        x = a[j]
                        c[j] = 1
                        #print("x:{}".format(x))
                #print("i:{}, j:{}, c:{}".format(i,j,c))
print(color)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
num_list = []
for i in range(n):
    num_list.append(int(input()))
# 広義単調減少部分列の最長を求める

## dp[i] := num_listのi番目までの数字が末尾となるような文字列の長さの最大 と定義すると
# 1.num_list[i]番目のみ
# 2.num_list[j] >= num_list[i] を満たす num_list[j] で終わる文字列の末尾にnum_list[i] をつける
# 1 もしくは 2をみたすものの中で最大のものがdp[i]

dp = [0] * n
dp[0] = 1

for i in range(1, n):
    add_previous = [0] # 2の条件を満たすものを入れる
    for j in range(0, i):
        if num_list[i] <= num_list[j]:
            add_previous.append(dp[j] + 1)
       
    dp[i] = max([1, max(add_previous)])
    
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
for i in range(N):
        x = int(input())
        a.append(x)
c = [0 for i in range(N)]
color = 0
for i in range(N-1,-1,-1):
        if sum(c) == N:
                #print("break:{}".format(i))
                break
        if c[i]: continue
        color += 1
        #print(color)
        x = a[i]
        c[i] = 1
        for j in range(i-1,-1,-1):
                if c[j]: continue
                if x > a[j]:
                        x = a[j]
                        c[j] = 1
                        #print("x:{}".format(x))
                #print("i:{}, j:{}, c:{}".format(i,j,c))
print(color)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = []
for i in range(N):
    A = int(input())
    for j in range(len(X)):
        if A > X[j]:
            X[j] = A
            break
    else:
        X.append(A)
print(len(X))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = []
for i in range(N):
    A = int(input())
    target = [x for x in X if x < A]
    if len(target) > 0:
        X[X.index(max(target))] = A
    else:
        X.append(A)
print(len(X))

Submission status: Time Limit Exceeded

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

for v in arr:
  check = 0
  for i in range(len(max_v)):
    if max_v[i] < v:
      max_v[i] = v
      check = 1
      break
  if check == 0:
    max_v.append(v)
print(len(max_v))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
arr = [int(input()) for i in range(N)]
max_v= []
for v in arr:
  check = 0
  for i, k in enumerate(max_v):
    if k < v:
      max_v[i] = v
      check = 1
      break
  if check == 0:
    max_v.append(v)
print(len(max_v))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
from sys import stdin


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [-1] * N
    ans = 0
    for _ in range(N):
        n = int(input())
        for i, a in enumerate(A):
            if n > a:
                A[i] = n
                ans = max(ans, i)
                break

    return ans + 1


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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
pre=[]
for i in a:
  if len(pre)==0:
    pre.extend([[i]])
  else:
    flg=0
    for j in range(len(pre)):
      if pre[j][-1] < i:
        pre[j].append(i)
        flg=1
        break
    if flg==0:
      pre.extend([[i]])
print(len(pre))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = []
B = []
for _ in range(N):
    x = int(input())
    i = bisect.bisect_left(A,x)
    j = bisect.bisect_right(A,x)
    if len(A) == 0:
        A.append(x)
    elif i > 0:
        if x <= A[i-1]:
            A.insert(i-1, x)
        else:
            A[i-1] = x
    elif x <= A[i]:
        A.insert(i, x)
    elif x > A[i]:
        A[i] = x

print(len(A))

Submission status: Time Limit Exceeded

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

temp = [A[0]]
for i in range(1,N):
  temp.sort(reverse=True)
  for j in range(len(temp)):
    if A[i] > temp[j]:
      temp[j] = A[i]
      break
  else:
    temp.append(A[i])

print(len(temp))

Submission status: Time Limit Exceeded

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

import math

if __name__ == '__main__':
    N = int(input())
    A = [int(input()) for c in range(N)]
    colors = [
        -1
    ]
    # R = [0 for i in range(N)]
    # M = 0

    for i in range(N):
        # print('i={}'.format(i))
        a = A[i]
        for j in range(len(colors)):
            if a > colors[j]:
                colors[j] = a
                break
        else:
            colors.append(
                a
            )
            colors.sort()

    print(len(colors))

Submission status: Time Limit Exceeded

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

import math

if __name__ == '__main__':
    N = int(input())
    colors = [
        -1
    ]
    # R = [0 for i in range(N)]
    # M = 0

    for i in range(N):
        # print('i={}'.format(i))
        a = int(input())
        for j in range(len(colors)):
            if a > colors[j]:
                colors[j] = a
                break
        else:
            colors.append(
                a
            )
            colors.sort()

    print(len(colors))

Submission status: Time Limit Exceeded

Solution code:
 
n = int(input())

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

color = [[-1] for i in range(n+1)]

max_j = 0
for i in range(n):
    for j in range(n):
        #print(color[j][-1])
        if a[i] > color[j][-1]:
            color[j].append(a[i])
            max_j = max(max_j,j+1)
            break
            
print(max_j)

Submission status: Time Limit Exceeded

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

lst = []
for i in range(N):
    flag = False
    for j in range(len(lst)):
        if lst[j] < A[i]:
            lst[j] = A[i]
            lst.sort(reverse = True)
            flag = True
            break
    if flag == False:
        lst.append(A[i])
        lst.sort(reverse = True)

print (len(lst))

Submission status: Time Limit Exceeded

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

lst = []
for i in range(N):
    flag = False
    for j in range(len(lst)):
        if lst[j] < A[i]:
            lst[j] = A[i]
            lst.sort(reverse = True)
            flag = True
            break
    if flag == False:
        lst.append(A[i])
        lst.sort(reverse = True)

print (len(lst))

Submission status: Time Limit Exceeded

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

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

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

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

import heapq

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

B = []

for a in A:
    i = 0
    while i < len(B) and B[i] >= a:
        i += 1

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

print(len(B))

pass

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

Submission status: Time Limit Exceeded

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

lenA = len(A)
cnt = 0
chk = [0]*lenA

for i in range(lenA):
    if chk[i]:
        continue
    chk[i] = 1

    last = A[i]
    for j, v in enumerate(A[i+1:]):
        if chk[i+j+1] or v<=last:
            continue
        else:
            chk[i+j+1] = 1
            last = v
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

lenA = len(A)
cnt = 0
chk = [0]*lenA

for i in range(lenA):
    if chk[i]:
        continue
    chk[i] = 1

    last = A[i]
    for j, v in enumerate(A[i+1:]):
        if chk[i+j+1] or v<=last:
            1 + 1
        else:
            chk[i+j+1] = 1
            last = v
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

n = 1
m = [A[0]]
for i in range(1, N):
  for j in range(n):
    if m[j] < A[i]:
      m[j] = A[i]
      break
  else:
    n += 1
    m.append(A[i])
print(n)

Submission status: Time Limit Exceeded

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

for i in range(1,n):
  tmpmin = tree[0]
  if a[i] > tmpmin:
  #  bisect.insort(tree, a[i])
  #else:
    index = bisect.bisect_left(tree, a[i])
    del tree[index - 1]
  bisect.insort(tree, a[i])
  #print(tree)
    
print(len(tree))

Submission status: Time Limit Exceeded

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

for i in range(1,n):
  tmpmin = tree[0]
  if a[i] <= tmpmin:
    bisect.insort(tree, a[i])
  else:
    index = bisect.bisect_left(tree, a[i])
    del tree[index - 1]
    bisect.insort(tree, a[i])
  #print(tree)
    
print(len(tree))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = []
for _ in range(N):
  A = int(input())
  D = 0
  for o,i in enumerate(ans):
    if A>i:
      ans[o] = A
      D = 1
      break
  if D == 0:
    ans.append(A)
  
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = [int(input())]
for k in range(N-1):
    t = int(input())
    if A[0] >= t:
        A = [t] + A
    else:
        A[bisect.bisect_left(A,t)-1] = t
print(len(A))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = []
for _ in range(N):
  A = int(input())
  D = 0
  for o,i in enumerate(ans):
    if A>i:
      ans[o] = A
      D = 1
      break
  if D == 0:
    ans.append(A)
  ans = sorted(ans, reverse = True)
  
print(len(ans))

Submission status: Time Limit Exceeded

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

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

n = int(input())
a = [int(input()) for _ in range(n)]
x = [False]*(n)
ans = 0
for i in range(n):
    if x[i] == False:
        ans += 1
        x[i] = True
    for j in range(i+1,n):
        if a[i] < a[j] and x[j] == False:
            x[j] = True

print(ans)

Submission status: Time Limit Exceeded

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

print(len(tmp))

Submission status: Time Limit Exceeded

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

print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
ans = []
for a in A:
    if bisect.bisect_left(ans,a) != 0:
        ans[bisect.bisect_left(ans,a)-1] = a
    else:
        ans.insert(0,a)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

Submission status: Time Limit Exceeded

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

print(len(tmp))

Submission status: Time Limit Exceeded

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

n = onem()

a = [onem() for i in range(n)]

d = [a[0]]
co = 1
for i in range(1,n):
	for j in range(len(d)):
		if d[-(j+1)] < a[i]:
			d.pop(len(d)-1-j)
			d.insert(len(d)-j,a[i])
			break
	else:
		co += 1
		d.append(a[i])
print(co)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
for i in range(N):
        x = int(input())
        a.append(x)
c = [0 for i in range(N)]
color = 0
for i in range(N-1,-1,-1):
        if sum(c) == N: break
        if c[i]: continue
        color += 1
        #print(color)
        x = a[i]
        c[i] = 1
        for j in range(i-1,-1,-1):
                if c[j]: continue
                if x > a[j]:
                        x = a[j]
                        c[j] = 1
                        #print("x:{}".format(x))
                #print("i:{}, j:{}, c:{}".format(i,j,c))
print(color)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
for i in range(N):
        x = int(input())
        a.append(x)
c = [0 for i in range(N)]
color = 0
for i in range(N-1,-1,-1):
        if c[i]: continue
        color += 1
        #print(color)
        x = a[i]
        c[i] = 1
        for j in range(i-1,-1,-1):
                if c[j]: continue
                if x > a[j]:
                        x = a[j]
                        c[j] = 1
                        #print("x:{}".format(x))
                #print("i:{}, j:{}, c:{}".format(i,j,c))
print(color)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
for i in range(N):
        x = int(input())
        a.append(x)
c = [0 for i in range(N)]
color = 0
for i in range(N-1,-1,-1):
        if c[i]: continue
        color += 1
        #print(color)
        x = a[i]
        c[i] = 1
        for j in range(i-1,-1,-1):
                if x > a[j] and c[j] == 0:
                        x = a[j]
                        c[j] = 1
                        #print("x:{}".format(x))
                #print("i:{}, j:{}, c:{}".format(i,j,c))
print(color)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(input())
ans = 1
idx = -1
A = [int(input()) for _ in range(N)]
ans = [[A[0]]]
flag = False
cnt = 0
for i in range(1, N):
    flag = False
    for j in range(len(ans)):
        if flag:
            break
        if ans[j][-1] < A[i]:
            ans[j].append(A[i])
            flag = True
            break
        cnt += 1
    else:
        ans.append([A[i]])
print(len(ans))

Submission status: Time Limit Exceeded

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


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

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

ans = len(color)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

from bisect import bisect_left

n = int(input())
a = int(input())

color = [a]
color_min = a

for _ in range(1, n):
    a = int(input())
    if color_min >= a:
        j = bisect_left(color, a)
        color.insert(j, a)
        color_min = a
    else:
        j = bisect_left(color, a)
        del color[j-1]
        j = bisect_left(color, a)
        color.insert(j, a)
        color_min = color[0]

print(len(color))

Submission status: Time Limit Exceeded

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

n = int(input())
a = int(input())

color = [a]
color_min = a

for _ in range(1, n):
    a = int(input())
    if color_min >= a:
        j = bisect.bisect_left(color, a)
        color = color[:j] + [a] + color[j:]
        color_min = a
    else:
        j = bisect.bisect_left(color, a)
        color = color[:j-1] + color[j:]
        j = bisect.bisect_left(color, a)
        color = color[:j] + [a] + color[j:]
        color_min = color[0]

print(len(color))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
ans = []
ans.append(A[0])
A.pop(0)
for a in A:
    c = 0
    for j in range(len(ans)):
        if ans[j] < a:
            ans[j] = a
            break
        else:
            c += 1
    if len(ans) == c:
        ans.append(a)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = [int(input()) for _ in range(N)]
lst = []
for A in A_list:
    next = -1
    for l in lst:
        if (l < A):
            next += 1
    if (next == -1):
        tmp = lst
        lst = [A]
        lst.extend(tmp)
    elif (next == len(lst)):
        lst.append(A)
    else:
        lst[next] = A
print(len(lst))

Submission status: Time Limit Exceeded

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

n = int(input())
a = int(input())

color = [a]
color_min = a

for _ in range(1, n):
    a = int(input())
    if color_min >= a:
        bisect.insort_left(color, a)
        color_min = a
    else:
        j = bisect.bisect_left(color, a)
        del color[j-1]
        bisect.insort_left(color, a)
        color_min = color[0]

print(len(color))

Submission status: Time Limit Exceeded

Solution code:
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
N = int(input())						# 5

from bisect import bisect_right as br
from bisect import bisect_left  as bl
from bisect import insort_right as ir
from bisect import insort_left  as il


a = int(input())
B=[a]

for i in range(1,N):
	a = int(input())

	r = br(B,a)
	if B[-1]==a:
		B.append(a)
	elif a>B[-1]:
		B[-1]=a
	elif a<B[0]:
		B = [a]+B
	else:
		B[r-1]=a


	p("  i,a,r,B ",i,a,r,B)


p("B",B)

print( len(B) )

Submission status: Time Limit Exceeded

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

n = int(input())
a = int(input())

color = [a]
color_min = a

for _ in range(1, n):
    a = int(input())
    if color_min >= a:
        bisect.insort_left(color, a)
        color_min = a
    else:
        j = bisect.bisect_left(color, a)
        color.pop(j-1)
        bisect.insort_left(color, a)
        color_min = color[0]

print(len(color))

Submission status: Time Limit Exceeded

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

n = int(input())
a = int(input())

color = [a]
color_min = a

for i in range(1, n):
    a = int(input())
    if color_min >= a:
        bisect.insort_left(color, a)
        color_min = a
    else:
        j = bisect.bisect_left(color, a)
        color.pop(j-1)
        bisect.insort_left(color, a)
        color_min = color[0]

print(len(color))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a = int(input())

color = [a]
color_min = a

for i in range(1, n):
    a = int(input())
    if color_min >= a:
        bisect.insort_left(color, a)
        color_min = a
    else:
        j = bisect.bisect_left(color, a)
        color.pop(j-1)
        bisect.insort_left(color, a)
        color_min = color[0]

print(len(color))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = [int(input()) for _ in range(N)]
from collections import deque
queue = deque()
for A in A_list:
    next = -1
    for q in queue:
        if (q < A):
            next += 1
    if (next == -1):
        queue.appendleft(A)
    elif (next == len(queue)):
        queue.append(A)
    else:
        queue[next] = A
print(len(queue))

Submission status: Time Limit Exceeded

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

d = []
for i in range(N):
  ite = 0
  flag = True
  for j in range(len(d)):
    if d[j] < A[i]:
      ite = j
      flag = False
      break
  if flag:
    d.append(A[i])
  else:
    d[ite] = A[i]
print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a = [0] * n

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

color = [a[0]]
color_min = a[0]

for i in range(1, n):
    if color_min >= a[i]:
        bisect.insort_left(color, a[i])
        color_min = a[i]
    else:
        j = bisect.bisect_left(color, a[i])
        color.pop(j-1)
        bisect.insort_left(color, a[i])
        color_min = color[0]

print(len(color))

Submission status: Time Limit Exceeded

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

count = 0
while(True):
  if len(a) == 0:
    break
  count += 1
  comp = a[0]
  del a[0]
  dif = 0
  for i in range(len(a)):
    idx = i-dif
    if a[idx] > comp:
      comp = a[idx]
      del a[idx]
      dif += 1
  # print(a)
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li = [-1]
len_ = 1
c = 1
b = -1
index = -1
ns = [int(input()) for _ in range(N)]

for n in ns:
    index = -1
    while n <= b:
        # try:
        if -index < len(li):
            index -= 1
            b = li[index]
        # except BaseException:
        else:
            c += 1
            li.append(n)
            break
    li[index] = b = n

print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
li = [-1]
len_ = 1
c = 1
b = -1
index = -1

for _ in range(N):
    n = int(input())
    index = -1
    while n <= b:
        # try:
        if -index < len(li):
            index -= 1
            b = li[index]
        # except BaseException:
        else:
            c += 1
            li.append(n)
            break
    li[index] = b = n

print(c)