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:
n = int(input())
a = [int(input()) for i in range(n)]
cnt=0
while len(a)>0:
  cnt+=1
  nokori=[]
  tmp = a[0]
  for i in range(1,len(a)):
    if tmp<a[i]:
      tmp=a[i]
    else:
      nokori.append(a[i])
  a = nokori
print(cnt)

Submission status: Time Limit Exceeded

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

'''
def solve(a, cur, nxt):
    for i in range(1, len(cur)):
        if cur[i] > a:
            a = cur[i]
        else:
            nxt.append(cur[i])

ans = 0
cur = A
nxt = []
while True:
    ans += 1
    a = cur[0]
    solve(a, cur, nxt)
    if len(nxt) == 0:
        break
    cur = nxt
    nxt = []
print(ans)
'''

B = [A[0]]
for i in range(1, N):
    a = A[i]
    found = False
    for j in range(len(B)):
        b = B[j]
        if a > b:
            B[j] = a
            found = True
            break
    if not found:
        B.append(a)

# print(B)
print(len(B))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys


def delete_left_maxvals(i, A):
    # Aのi番目要素よりも左側にあって、かつ、左側領域において最大となるものを削除
    A_left = A[:i]
    if len(A_left) == 0:
        A.pop(i)
        return A
    
    max_index = A_left.index(max(A_left))
    A.pop(i)

    delete_left_maxvals(max_index, A)
    return A


def solve(N: int, A: "List[int]"):
    num_colors = 0

    while True:
        max_idx = A.index(max(A))
        A = delete_left_maxvals(max_idx, A)
        
        num_colors += 1
        if len(A) == 0:
            break
    print(num_colors)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

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

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

ans = 0
A_new = A.copy()
while A_new:
    ans += 1
    m = -1
    removal_list = []
    for idx in range(len(A_new)):
        if m < A_new[idx]:
            m = A_new[idx]
            removal_list.append(idx)
    A_new = [x for (i, x) in enumerate(A_new) if i not in removal_list]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

lasts=[int(input())]
for _ in range(N-1):
    a=int(input())
    
    if a<=lasts[0]:
        lasts.insert(0, a)
    else:
        for i,val in enumerate(lasts[::-1]):
            if val<a:
                lasts[len(lasts)-1-i]=a
                break

print(len(lasts))

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
not_used1 = [i for i in range(N)]
not_used2 = [i for i in range(N)]
while 1:
  temp = -1
  for i in not_used1:
    if temp<A[i]:
      temp = A[i]
      all_counter += 1
      not_used2.remove(i)
  not_used1 = not_used2[:]
  counter += 1
  if all_counter==N:
    break
  
print(counter)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
alist = [int(input()) for _ in range(n)]
argsort = [i for i, v in sorted(enumerate(alist), key=lambda x: x[1])]
used = [0 for _ in range(n)]

num_color = 0
while sum(used) < n:
    for ai, i in enumerate(argsort):
        if used[i] == 0:
            st_ai = ai
            st_i = i
            used[i] = 1
            break
    num_color += 1
    for i in argsort[st_ai+1:]:
        if used[i] == 0 and st_i < i and alist[st_i] != alist[i]:
            st_i = i
            used[i] = 1

print(num_color)

Submission status: Time Limit Exceeded

Solution code:
import bisect


N = int(input())

lis = []

A1 = int(input())


lis.append(A1)


for i in range(N-1):

    A = int(input())

    flag = True
    ins = bisect.bisect_left(lis,A)

    if ins == 0:
        B = [A] + lis
        lis = B.copy()

    if lis[ins-1] < A:
        lis[ins-1] = A

"""
    for l in lis:

 

        if l < A:
            l = A
            flag = False
            lis.sort()
            maxi = max(maxi , i)
            break

    if flag:
        lis.append(A)
"""

#print (lis)
print (len(lis))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
top = [-1 for i in range(n)]
for i in range(n):
    a = int(input())
    if top[-1] < a:
        top[-1] = a
    else:
        temp = np.searchsorted(top,a)
        top[temp-1] = a

head = 0
for i in range(n):
    if top[i] != -1:
        head = i
        break

# print(top)
print(n-head)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())    
color_list =  [int(input())]
for i in range(N-1):
    new_value = int(input())
    if(new_value > color_list[0]):
        color_list[0] = new_value
    elif(new_value <= color_list[-1]):
        color_list.append(new_value)
    else:
        for i in range(len(color_list)):
            if(new_value > color_list[i]):
                color_list[i] = new_value
                break
print(len(color_list))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self, number_list):
        self.root = None
        self.ans = 1
        self.leftMin = 0
        self.leftestNode = None
        for node in number_list:
            self.insert(node)

    def insert(self, data):
        n = self.root #nにルートを代入
        if n == None: #ルートに何も入っていない場合
            self.root = Node(data) #ルートにノードを代入(二分探索木の一番上の部分が出来る)
            return #呼び出し部分に戻る
        else: #ルートノードに既に数値が入ってる場合
            while True: #return等が入るまでずっと実行
                entry = n.data #entryにnが持つデータ(数値)を入れる
                if data <= entry: # 左
                    if n.left is None: #nの左エッジに何も入っていない場合
                        n.left = Node(data) #nの左エッジにdata(代入するデータ)を代入
                        self.leftestNode = n.left
                        self.ans += 1
                        return ##呼び出し部分に戻る
                    if self.leftMin >= data :
                        self.leftMin = data
                        self.leftestNode.left = Node(data)
                        self.ans += 1
                        return
                    n = n.left #nの左に何か入っている場合nにnのleftを代入
                else: #entryとdata(代入するデータ)を比較してentryの方が小さい場合
                    if n.right is None: #nの右エッジに何も入っていない場合
                        n.right = Node(data) #nの右エッジにdata(代入するデータ)を代入
                        return #呼び出し部分に戻る
                    n.data = max(n.data, data)
                    return
    def getAns(self) :
        return self.ans


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

tree = BST(A)

print(tree.getAns())

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=[0]
j=0
f=-1
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.append(s[i])
    f=0
    j=0
    i+=1
print(len(ans))

Submission status: Time Limit Exceeded

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

ans = 0

rm = []
remain = []
before = A[0]

while True:
    for i in range(1, len(A)):
        if before < A[i]:
            rm.append(A[i])
            before = A[i]
        else:
            remain.append(A[i])
    ans = ans + 1
    A = remain
    remain = []
    rm = []
    if len(A) == 0:
        break
    before = A[0]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
numofcolor = 1
A = [0] * N
for i in range(N):
    A[i] = int(input())
listofmax = [A[0]]
lenoflistofmax = 1  # 実際のところnumofcolorと同じ値になる
for j in range(1, N):
    if listofmax[0] >= A[j]:
        numofcolor += 1
        lenoflistofmax += 1
        listofmax.insert(0, A[j])
    else:
        listofmax[bisect.bisect_left(listofmax, A[j]) - 1] = A[j]
print(numofcolor)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

list_ = [As[0]]
for a in As[1:]:
    i = bisect_left(list_, a) - 1
    if i < 0:
        list_.insert(0, a)
    else:
        list_[i] = a
print(len(list_))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ans = [A[0]]
# print(ans)

for a in A[1:]:
    if a <= ans[0]:  # 色を増やすしかない
        ans.append(a)
        ans.sort()
    else:  # 既存の色のどこかに追加
        idx = bisect.bisect_left(ans, a)
        ans[idx-1] = a
    # print(a, ans)

# print(ans)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
C = [-1]
count = 1
for num in A:
    find = False
    for i, maxi in enumerate(C):
        if maxi < num:
            C[i] = num
            find = True
            break     
    if not(find):
        C.append(num)
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())

L = [int(input())]
for _ in range(N - 1):
    a = int(input())
    if a <= L[0]:
        L.insert(0, a)
        continue

    i = bisect.bisect_left(L, a)
    L[i - 1] = a

print(len(L))

Submission status: Time Limit Exceeded

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

ans = 0

while(a!=[]):
    t = a.pop(0)
    ans += 1
    for i in a:
        if t < i:
            a.remove(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = 0

color_group = []
a1 = int(input())
color_group.append([a1])

for n in range(N-1):
  a2 = int(input())
  nm_of_group = len(color_group)
  for i in range(1, nm_of_group+1):
    if color_group[-i][-1] < a2:
      color_group[-i].append(a2)
      break
  else:
    color_group.append([a2])

ans = len(color_group)
print(ans)

Submission status: Time Limit Exceeded

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

tree = [[A[0]]]
leaf = [A[0]]
for n in range(1,N):
    a = A[n]
    pos = min(n-1,bisect.bisect_left(leaf,a)-1)
    if pos==-1:
        tree = [[a]] + tree
        leaf = [a] + leaf
    else:
        tree[pos].append(a)
        leaf[pos] = a
print(len(tree))

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_right, insort_left

def I(): return int(sys.stdin.readline())

def main():
  n = int(input())
  a = [I() for i in range(n)]
  b = []

  for i in range(n-1, -1, -1):
    #print(a[i])
    t = bisect_right(b, a[i])
    if len(b)-1<t or b[t]==a[i]:
      insort_left(b, a[i])
    else:
      b[t] = a[i]
    #print(b)
  print(len(b))

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def remove_all(l,val):
    while 1:
        if not val in l:
            return
        l.remove(val)

N = int(input())
A = [int(input()) for i in range(N)]
count = 0
for i in A:
    for j in A:
        if i < j:
            remove_all(A, j)
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [a[0]]

for i in range(1,n):
#    print(c)
#    print(p)
    if c[0] >= a[i]:
        c.insert(0,a[i])
    else:
        p = bisect.bisect_left(c, a[i])
        c[p-1]=a[i]
#        c.sort()

print(len(c))

Submission status: Time Limit Exceeded

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



mina = [A[0]]

# print(mina)
# ans = 
for i in range(1,N):
    # print(mina)
    if mina[0]>=A[i]:
        ind = bisect.bisect_left(mina,A[i])
        mina.insert(ind,A[i])
        # ans +=1 
    else:
        ind = bisect.bisect_left(mina,A[i])
        mina.insert(ind,A[i])
        if ind == len(mina)-1:
            
            del(mina[-2])
        else:
            # print("a")
            del(mina[ind-1])


# print(mina)
    
print(len(mina))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
count=0
for i in range(n):
    a.append(int(input()))
for k in range(n):
    if a[k]!=-1:
        temp=a[k]
        a[k]=-1
        count+=1
        for i in range(n):
            if temp<a[i]:
                temp=a[i]
                a[i]=-1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

answer = [-1]
for i in range(n):
    input_num = int(input())
    list_num = len(answer)
    exist = False
    for index, a  in enumerate(answer[::-1]):
        if input_num > a:
            answer[list_num - index - 1] = input_num
            exist = True
            break
    if not exist:
        answer.append(input_num)

print(len(answer))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
b = [1000000000]
ans = 1
for i in range(n):
  m = int(input())
  a.append(m)
  if i == 0:
    continue
  elif a[i-1] < a[i]:
    continue
  elif a[i] > b[0]:
    b.append(a[i])
    b.sort()
  else:
    b.append(a[i])
    ans += 1
    b.sort()
print(ans)

Submission status: Time Limit Exceeded

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

C = [[A[0]]]
head = [A[0]]
for i in range(N-1):
    for j, h in enumerate(head):
        if A[i+1] > h:
            C[j].append(A[i+1])
            head[j] = A[i+1]
            break
    else:        
        C.append([A[i+1]])  # new color
        head.append(A[i+1])

print(len(C))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7
 
debug = True
debug = False
 
def dprint(*objects):
    if debug == True:
        print(*objects)
 
def main():
    N = II()
    a_list = []
 
    for i in range(N):
        a = II()
        a_list.append(a)
 
 
    g = []
 
    from bisect import bisect_left
 
    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.append(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                g.insert(0, a)
    dprint(g)
    print(len(g))
main()

Submission status: Time Limit Exceeded

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

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

ans = 0
q = [A[0]]
p = A[0]
for i in range(1,N):
    insert_index = bisect_left(q,A[i])
    if p >= A[i] and insert_index == 0:
        q = [A[i]] + q
        ans += 1
    else:
        q[insert_index-1] = A[i]
    p = A[i]

print(len(q))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = []
for i in range(n):
  inp = int(input())
  for i in range(len(lst)):
    if inp > lst[i]:
      lst[i] = inp
      break
  else:
    lst.append(inp)
print(len(lst))

Submission status: Time Limit Exceeded

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

ans = [-1]
for i in range(n):
    tmp = list(map(lambda x: x-a[i], ans))
    index = 0
    if(min(tmp) >= 0):
        ans.append(a[i])
    else:
        xx = len(ans)
        for i in range(xx):
            if(tmp[i] >= 0):
                tmp[i] = -1000000000
        index = tmp.index(max(tmp))
        ans[index] = a[i]
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect


N = int(input())

lis = []

A1 = int(input())


lis.append(A1)


for i in range(N-1):

    A = int(input())

    flag = True
    ins = bisect.bisect_left(lis,A)

    if ins == 0:
        lis.insert(0,A)

    if lis[ins-1] < A:
        lis[ins-1] = A

"""
    for l in lis:

 

        if l < A:
            l = A
            flag = False
            lis.sort()
            maxi = max(maxi , i)
            break

    if flag:
        lis.append(A)
"""

#print (lis)
print (len(lis))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())
c = 0
la = len(a)-1
while la >= 0:
    m = a[la]
    for i in range(la-1,-1,-1):
        if m > a[i]:
            m = a[i]
            del a[i]
            la -= 1
    if len(a) > 0:
        c += 1
    la -= 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
a=[int(input())]
for _ in [0]*(n-1):
    new=int(input())
    if a[-1]>=new:a.append(new)
    else:
        for j in range(len(a)):
            if a[j]<new:a[j]=new;break
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
    n = int(input())

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

    l_unique = list(set(a))
    l_unique_sorted = sorted(l_unique)

    colors = 0
    index = 0
    while len(a) != 0:
        if not l_unique_sorted[index] in a:
            index += 1
            continue

        st_point = a.index(l_unique_sorted[index])

        tmp_max = a[0]
        remove_list = [tmp_max]
        for i in range(st_point, len(a)):
            if tmp_max < a[i]:
                remove_list.append(a[i])

        for i in remove_list:
            a.remove(i)

        colors += 1

    print(colors)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math

def search(S):

    for i, a in enumerate(A):
        if a < S:
            A[i] = S
            return 
    return



def main():
    N = int(input())
    A[0] = int(input())
    m = A[0]
    for _ in range(N-1):
        S = int(input())
        if S <= m:
            A.append(S)
        else:
            search(S)
        m = A[-1]
    print(len(A))

    

if __name__ == "__main__":
    A = [0]
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
left = 0
ans = 1
l = 1
pre = A[0]
right = 1
while N > 1:
    if right >= N:
        N -= 1
        A.pop(left)
        l = 1
        ans += 1
        right = left+1
        pre = A[left]
    elif pre < A[right]:
        l += 1
        pre = A.pop(right)
        N -= 1
    else:
        right += 1
print(ans)

Submission status: Time Limit Exceeded

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

S = [[A[0]]]
s = {A[0]: [0]}
for _ in A[1:]:
    ins = False
    for v in sorted(set(s.keys()), reverse=True):
        if v < _:
            i = s[v].pop()
            if len(s[v]) == 0:
                del s[v]
            S[i].append(_)
            if _ in s:
                s[_].append(i)
            else:
                s[_] = [i]
            ins = True
            break
    if ins is False:
        S.append([_])
        if _ in s:
            s[_].append(len(S)-1)
        else:
            s[_] = [len(S)-1]
print(len(S))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
now_top = -1
color = 1
prev_tops = []
for n in range(N):
    x = int(input())
    if x > now_top:
        now_top = x
    else:
        b = bisect.bisect_left(prev_tops, x)
        if b == 0:
            prev_tops.append(now_top)
            color += 1
            now_top = x
        else:
            b = b - 1
            push = now_top
            now_top = prev_tops[b]
            prev_tops = prev_tops[:b] + prev_tops[b+1:]
            prev_tops.append(push)
        prev_tops.sort()
print(color)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

from collections import defaultdict
COLOR = defaultdict(lambda: -1)

for b in BALL:
    i = 0
    while True:
        if COLOR[i] < b:
            COLOR[i] = b
            break
        i += 1
            
#print(COLOR)
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

A=[]

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

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


B=[-1]

for i in range(N):
	a = A[i]
	p("i,a",i,a)
	
	for j in range(1,len(B)+1):
		if B[-j]<a:
			 B[-j]=a
			 break
	else:
		B.append(a)

	p("  i, B",i,B)


p("A",A)
p("B",B)

print( len(B) )

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

print(len(x))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

# edge = [1, 2, 5]
# pos = bisect.bisect_left(edge, 6)
# print(pos)

edge = [a[0]]
l = 1
for v in a[1:]:
    pos = bisect.bisect_left(edge, v)
    # print(edge, v, pos)
    if pos == 0:
        edge.insert(0, v)
    else:
        # value = edge[pos - 1]
        # del edge[pos - 1]
        # edge.insert(v, bisect.bisect_left(edge, v))
        edge[pos - 1] = v
print(len(edge))

Submission status: Time Limit Exceeded

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

def longest_increasing_subsequence(X):
    """Returns the Longest Increasing Subsequence in the Given List/Array"""
    N = len(X)
    P = [0] * N
    M = [0] * (N+1)
    L = 0
    for i in range(N):
       lo = 1
       hi = L
       while lo <= hi:
           mid = (lo+hi)//2
           if (X[M[mid]] < X[i]):
               lo = mid+1
           else:
               hi = mid-1
 
       newL = lo
       P[i] = M[newL-1]
       M[newL] = i
 
       if (newL > L):
           L = newL
 
    S = []
    S_ind = []
    k = M[L]
    for i in range(L-1, -1, -1):
        S.append(X[k])
        S_ind.append(k)
        k = P[k]
    return S[::-1], S_ind[::-1]

cnt = 0
while len(A) != 0:
    _, ind = longest_increasing_subsequence(A)
    A = np.delete(A, ind)
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(input()) for i in range(n)]
tmp=[-1]*n
ans=0
for i in range(n):
  for j in range(n):
    if tmp[j]<a[i]:
      if tmp[j]==-1:ans+=1
      tmp[j]=a[i]
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
cnt=0
while len(a)>0:
  cnt+=1
  nokori=[]
  tmp = a[0]
  for i in range(1,len(a)):
    if tmp<a[i]:
      tmp=a[i]
    else:
      nokori.append(a[i])
  a = nokori
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
numofcolor = 1
A = [0] * N
for i in range(N):
    A[i] = int(input())
listofmax = [A[0]]
lenoflistofmax = 1  # 実際のところnumofcolorと同じ値になる
for j in range(1, N):
    if bisect.bisect_left(listofmax, A[j]) == 0:
        numofcolor += 1
        lenoflistofmax += 1
        listofmax.insert(0, A[j])
    else:
        listofmax[bisect.bisect_left(listofmax, A[j]) - 1] = A[j]
print(numofcolor)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
sln = []


def update_solution(sln, k):
    ln = len(sln)
    for j in range(ln):
        if sln[ln - j - 1] < k:
            sln[ln - j - 1] = k
            return sln

    return [k] + sln


for i in range(n):
    sln = update_solution(sln, int(input()))

print(len(sln))

Submission status: Time Limit Exceeded

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

ans = [-1]
for i in range(n):
    tmp = list(map(lambda x: x-a[i], ans))
    index = 0
    if(min(tmp) >= 0):
        ans.append(a[i])
    else:
        for i in range(len(ans)):
            if(tmp[i] >= 0):
                tmp[i] = -1000000000
        index = tmp.index(max(tmp))
        ans[index] = a[i]
print(len(ans))

Submission status: Time Limit Exceeded

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

ite=0
ret=1
tmp=0
leng=N
flg=False
#print()
while leng > 0:
    #print(tmp,ite,AN[ite],ret)
    if (flg==False)and ite==0:
        flg=True
        tmp=AN.pop(ite)
        leng-=1
        continue
    if tmp < AN[ite]:
        tmp=AN.pop(ite)
        leng-=1
    else:
        ite+=1
        if ite >= leng:
            ite=0
            tmp=0
            flg=False
            ret+=1

print(ret)

Submission status: Time Limit Exceeded

Solution code:
#input = raw_input

N = int(input())

next_add_i = 0


#in_pairs = [[i, int(input())] for i in range(N)]
#sort_pairs = sorted(in_pairs, key=lambda x: -x[1])
#
#chikai_indexs = [None for _ in range(N)]
#for i, A in sort_pairs:
#    if i == 0:
#        last_i = i
#    else:
#        if last_i < i:



#for i, A in enumerate(A):
for i in range(N):
    A = int(input())

    if i == 0:    
        curs = [A]
        #sort_curs = [[A, next_add_i]]
        sort_curs = [A]
        #count = 1
        next_add_i += 1
    
    else:
        # find_max
        #print("sort_curs", sort_curs)
        #if sort_curs[-1][0] >= A: # if all
        if sort_curs[-1] >= A: # if all
            sort_curs.append(A)
            #sort_curs.append([A, next_add_i])
            next_add_i += 1

        else:
            #for sort_i, (cur_last_A, add_i) in enumerate(sort_curs):
            for sort_i, cur_last_A in enumerate(sort_curs):
                if cur_last_A < A:
                    #sort_curs[sort_i][0] = A
                    sort_curs[sort_i] = A
                    break

print(next_add_i)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=[]
for i in range(n):
    x=int(input())
    arr.append(x)
ans=[]
for i in range(n):
    if len(ans)==0:
        ans.append([arr[i]])
    else:
        flag=False 
        for j in range(len(ans)):
            if ans[j][-1]<arr[i]:
                ans[j].append(arr[i])
                flag=True
                break
        if not flag:
            ans.append([arr[i]])
# print(ans)
print(len(ans))

Submission status: Time Limit Exceeded

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

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

c = []

ans = 0

for a in A:
    if len(c) == 0:
        c.append(a)
    elif a <= c[0]:
        c = [a] + c
    else:
        i = bisect.bisect_left(c, a) - 1
        c[i] = a

print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

print(len(ans))

Submission status: Time Limit Exceeded

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

N=int(input())
A=[int(input()) for _ in range(N)]
l=[]
n=-1
for x in A:
    if n<x:
        n=x
    elif len(l)>0:
        tmp=bisect.bisect_left(l,x)
        if tmp==0:l=[x]+l
        else:
            l[tmp-1]=x
    else:l.append(x)
print(len(l)+1)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
mins = []
for i in range(N):
    A = int(input())
    b = bisect.bisect_left(mins, A)
    if b == 0:
        mins.append(A)
    else:
        mins[b-1] = A
    mins.sort()
print(len(mins))

Submission status: Time Limit Exceeded

Solution code:
#!/snap/bin/pypy3

import bisect


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

    logger = [A[0]]

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


    print(len(logger))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    N = II()
    a_list = []

    for i in range(N):
        a = II()
        a_list.append(a)

    g = []

    from bisect import bisect_left

    for i in range(N):
        a = a_list[i]
        if len(g) == 0:
            g.append(a)
        else:
            pos = bisect_left(g, a)
            dprint(g, a, pos)
            if pos >= 1:
                g[pos-1] = a
            else:
                g = [a] + g
    dprint(g)
    print(len(g))
main()