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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

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

    colors = 0
    while len(a) != 0:
        tmp_max = a[0]
        remove_list = [tmp_max]
        for ele in a:
            if tmp_max < ele:
                remove_list.append(ele)
                tmp_max = ele

        for i in remove_list:
            a.remove(i)

        colors += 1

    print(colors)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
n = int(input())
a = [0 for _ in range(n)]
for i in range(n):
    a[i] = int(input())


colors = defaultdict(int)
colors[a[0]] += 1
for num in a[1:]:
    for cnum in sorted(set(colors.keys()), reverse=True):
        if num > cnum:
            if colors[cnum] == 1:
                colors.pop(cnum)
            else:
                colors[cnum] -= 1
            break
    colors[num] += 1
print(sum(colors.values()))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import bisect
from collections import deque

dp = deque([])
n = ni()

for i in range(n):
    a = ni()
    if i == 0:
        dp.append(a)
        continue
    d = list(dp)
    f = bisect.bisect_left(d,a)
    if f == 0:
        dp.appendleft(a)
    else:
        d[f-1] = a
        dp = deque(d)

print(len(dp))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
prevMaxs = []
for i in range(n):
    num = int(input())
    if len(prevMaxs) == 0 :
        prevMaxs.append(num)
    else:
        key = bisect.bisect_left(prevMaxs, num)
        if key == 0:
            prevMaxs.insert(0, num)
        else:
            prevMaxs[key - 1] = num
print(len(prevMaxs))

Submission status: Time Limit Exceeded

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

X = [-1]

for a in A:
    for i in range(len(X)):
        if a > X[i]:
            X[i] = a
            break
    else:
        X.append(a)

print(len(X))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

A = np.zeros(n)
for i in range(n):
	A[i] = int(input())

arr = np.zeros(n)
cnt = 1

arr[0] = A[0]

for i in range(1,n):
    if A[i] <= np.min(arr[0:i]):
        arr[cnt] = A[i]
        cnt += 1
    else:
        ind = np.argmax(arr[0:i])
        arr[ind] = A[i]

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
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 _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

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

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

res = [] 
for a in A:
    if len(res) == 0:
        res.append(a)
        res.sort()
    else:
        if a <= res[0]:
            # 小さいので追加
            res = [a] + res
        else:
            # 入れ替え
            p = bisect.bisect_left(res, a)
            res[p-1] = a
print(len(res))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(input())]
for i in range(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
    a.sort(reverse=True)
print(len(a))

Submission status: Time Limit Exceeded

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

stack = []

for i, a in enumerate(A):
    if i == 0:
        stack.append([a])
    else:
        stack.sort(key=lambda x: max(x), reverse=True)
        for s in stack:
            if max(s) < a:
                s.append(a)
                break
        else:
            stack.append([a])
print(len(stack))

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())

tops = []

for i in range(n):
  x = int(input())
  inserted = False
  for j in range(len(tops)):
    if tops[j] < x:
      tops[j] = x
      inserted = True
      break
      
  if not inserted:
    tops.append(x)

print(len(tops))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq

n=int(input())
a1=int(input())
alist=[a1]

for i in range(n-1):
    an=int(input())
    if an<=alist[0]:
        alist=[an]+alist
    else:
        index = bisect.bisect_left(alist, an)
        alist[index-1]=an

print(len(alist))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

n = int(input())
a = [int(input()) for _ in range(n)]
res = [a[0]]
for x in a[1:]:
    if x <= res[0]:
        res.insert(0, x)
    else:
        res[bisect_left(res, x) - 1] = x

print(len(res))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
cnt = 0
m = [0] * n
for i in range(0, n):
    for j in range(cnt):
        if m[j] < a[i]:
            m[j] = a[i]
            break
    else:
        m[cnt] = a[i]
        cnt += 1
print(cnt)

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] > min(b):
    del b[b.index(min(b))]
    b.append(a[i])
  else:
    b.append(a[i])
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele > ref:
            left.append(ele)
        elif ele < ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

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

color = []
color.append(a.pop(0))
clen = 1
for ai in a:
    for i, c in enumerate(color): 
        if ai > c:
            color[i] = ai
            color = quick_sort(color)
            break
        else:
            if i+1 == clen:
                color.append(ai)
                clen += 1
                break
print(clen)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,*A=map(int,open(0).read().split())
color=np.array([-1])
for a in A:
    if a<=color.min():
        color = np.append(color,a)
    else:
        close_a = color[color<a].max()
        close_a_index = np.where(color==close_a)[0][0]
        color[close_a_index] = a
print(color.size)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

for i in range(N):
    hoge = bisect.bisect_left(result,S[i])
    if hoge == 0:
        result = [S[i]] + result
    else:
        result[hoge - 1] = S[i]
print(len(result))

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(N):
    start = A[i]
    if start == -1:
        continue
    cnt += 1
    for j in range(i+1,N):
        if start < A[j]:
            start = A[j]
            A[j] = -1

print(cnt)

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)
    p = bisect.bisect_left(c, a[i])
#    print(p)
    if p ==0:
        c.insert(0,a[i])
    else:
        c[p-1]=a[i]
#        c.sort()

print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


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

    c = [a.pop(0)]
    ans = 1

    for i in a:
        for ci in range(len(c)):
            if c[ci] < i:
                c[ci] = i
                break
        else:
            c.append(i)
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

X = [[-1]]

for a in A:
    for i in range(len(X)):
        if a > X[i][-1]:
            X[i].append(a)
            break
    else:
        X.append([a])

print(len(X))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[-1]
for _ in range(n):
    x=int(input())
    if a[-1]>=x:
        a.append(x)
    else:
        for i in range(len(a)):
            if a[i]<x:
                a[i]=x
                break
print(len(a))

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.insert(0, a)
    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:
import sys
import bisect
input=sys.stdin.readline

N=int(input())
A=[int(input()) for _ in range(N)]
l=[]
for x in A:
    if 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))

Submission status: Time Limit Exceeded

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

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)
    p = bisect.bisect_left(c, a[i])
#    print(p)
    if p ==0:
        c.insert(0,a[i])
    else:
        c[p-1]=a[i]
        c.sort()

print(len(c))

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_right, insort_left
N = int(sys.stdin.readline())
a_list = [int(sys.stdin.readline()) for _ in range(N)]


que = []

ans = 0
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        ans += 1
    else:
        idx = bisect_right(que, a-1)
        if idx == 0:
            insort_left(que, a)
            ans += 1
        else:
            que[idx-1] = a

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
n=int(input())
r=[]
for _ in range(n):
    a=int(input())
    if not r:
        r.append(a)
        continue
    i=bisect_left(r,a)
    if i:
        r.insert(i,a)
        del r[i-1]
    else:
        r=[a]+r
print(len(r))

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=[]
#B=[0]

a = int(input())
A.append(a)
#c = a
#C=[c]

for i in range(1,N):
	a = int(input())
	A.append(a)
#	B.append(a-A[i-1])
#	if c<a:
#		C[-1]=a
#	else:
#		C.append(a)
#	c=a

#p("A",A)
#p("B",B)
#p("C",C)

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

p("A",A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import heapq

N = int(stdin.readline().rstrip())
A = [int(input()) for i in range(N)]

tmp = []

for i in range(N):

    # print(tmp)

    if i == 0:
        tmp.append(A[i])
        continue

    jj = None
    minimum = 10 ** 5 + 1
    for j in range(len(tmp)):
        if A[i] - tmp[j] > 0:
            if minimum > A[i] - tmp[j]:
                # print(minimum)
                #print(A[i] - tmp[j])
                minimum = A[i] - tmp[j]
                jj = j

    if jj == None:
        tmp.append(A[i])
    else:
        tmp[jj] = A[i]

# print(tmp)
print(len(tmp))

Submission status: Time Limit Exceeded

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

list_ = [As[0]]
for a in As[1:]:
    if a > list_[0]:
        list_[0] = a
    elif a <= list_[-1]:
        list_.append(a)
    else:
        for i, l in enumerate(list_):
            if a > l:
                list_[i] = a
                break
print(len(list_))

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())

ans = 1
tops = [A[0]]
tops_cnt = 1
for i in range(1,N):
    for max_i in range(tops_cnt):
        if tops[max_i] < A[i]:
            tops[max_i] = A[i]
            break
    else:
        tops.append(A[i])
        ans += 1
        tops_cnt += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = [int(input()) for i in range(N)]
color=0
for i in range(N):
    j=A[i]
    A[i]=-1
    if j!=-1:
        color+=1
        for k in range(i+1,N):
            if A[k]>j:
                j=A[k]
                A[k]=-1
print(color)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = [int(input())for _ in range(N)]
li = [-1]
for i in A[::-1]:
    if(max(li)<i):
        li.append(i)
    else:
        ind = bisect.bisect_right(li,i)
        if(ind>=len(li)):
            li.append(i)
        elif(li[ind]>i):
            li.pop(ind)
            li.insert(ind,i)
        else:
            li.pop(ind+1)
            li.insert(ind+1)
print(len(li)-1)

Submission status: Time Limit Exceeded

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

A = sorted(A, key=lambda x: (x[1], -1 * x[0]))
# print(A)

memo = []
for a in A:
    num = a[0]
    already = False
    for i, m in enumerate(memo):
        if m <= num:
            memo[i] = num
            already = True
            break
    if not already:
        memo.append(num)
print(len(memo))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[-int(input())]
l=1
for i in range(1,n):
  b=-int(input())
  if a[-1]>b:
    if a[0]>b:a[0]=b;continue
    ok=l
    ng=0
    c=ok//2
    while ng+1<ok:
      if b<a[c]:ok=c
      else:ng=c
    a[ok]=b
  else:a.append(b);l+=1
print(l)

Submission status: Time Limit Exceeded

Solution code:

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

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n = int(input())
ans = [int(input())]
for i in range(n-1):
    now = int(input())
    j = bisect_left(ans,now)
    if j == 0:
        ans.insert(0,now)
    else:
        ans[j-1] = now

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

color = [float("inf")]
min_color = color[0]
for i in a:
    if i <= min_color:
        color = [i] + color
        min_color = i
    else:
        insert = bisect.bisect_left(color, i)
        del color[insert - 1]
        bisect.insort(color, i)
        if insert == 1:
            min_color = color[0]
print(len(color) - 1)

Submission status: Time Limit Exceeded

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


def solve():
    N = int(input())
    A = []
    checked = [False for _ in range(N)]
    count = 0
    for _ in range(N):
        A.append(int(input()))
    for i, a in enumerate(reversed(A)):
        i = N - 1 - i  # reversed index
        # print('searching:', i, ',', a)
        if checked[i]:
            # print('checked')
            continue
        count += 1
        searching = a
        for j, b in enumerate(reversed(A[:i])):
            # print(A[:i])
            j = i - j - 1
            # print(i, j, b)
            if b >= searching or checked[j]:
                continue
            searching = b
            checked[j] = True
            # print('check:', j, ',', b)
    return count
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
color=np.array([-1])
for i in range(n):
    a=int(input())
    if a<=color.min():
        color = np.append(color,a)
    else:
        close_a = color[color<a].max()
        close_a_index = np.where(color==close_a)[0][0]
        color[close_a_index] = a
print(color.size)

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
        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: #entryとdata(代入するデータ)を比較してentryの方が大きい場合
                    if n.left is None: #nの左エッジに何も入っていない場合
                        n.left = Node(data) #nの左エッジに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())
a_list = [int(input()) for _ in range(N)]

from bisect import *

que = []

ans = 0
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        ans += 1
    else:
        idx = bisect_right(que, a-1)
        if idx == 0:
            insort_left(que, a)
            ans += 1
        else:
            # b = que[idx-1]
            #if a != b:
            que[idx-1] = a
            #idx2 = bisect_right(que, a-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
# A=[int(input()) for _ in range(N)]
A=[]
ans=0
for i in range(N):
    A.extend([int(input())])
    if i==0:
        ans+=1
    else:
        if min(A[0:i])>=A[-1]:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n = int(input())
A=[int(input()) for _ in range(n)]
row = []
for a in A:
    if (not row) or a<=min(row):
        row.append(a)
    else:
        row[len(row) - bisect_left(row[::-1],a)] = a
print(len(row))

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

lis = []

A1 = int(input())

lis.append([A1])


for i in range(N-1):

    A = int(input())

    flag = True

    for l in lis:

        if l[-1] < A:
            l.append(A)
            flag = False
            break

    if flag:
        lis.append([A])

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

Submission status: Time Limit Exceeded

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

import bisect
#print(ans,a)
for i in range(1,n):
  j = bisect.bisect_left(ans,a[i])
  #print(j)
  if j == 0:
    ans = [a[i]] + ans
  else:
    ans[j-1] = a[i] 

print(len(ans))

Submission status: Time Limit Exceeded

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

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    from pathlib import Path
    parentdir = Path(os.path.dirname(__file__)).parent
    inputfile = parentdir.joinpath('test/sample-1.in')
    if len(sys.argv) == 1:
        set_stdin(inputfile)
# }}}

def solve():
    n = int(input())
    a = []
    
    col = 1

    for _ in range(n):
        a.append(int(input()))
    
    if n == 1:
        print(col)
        exit()

    b = [a[0]]

    for i in range(1,n):
        x = bisect_left(b,a[i])
        
        if x == 0:
            col += 1
            b = [a[i]] + b
        else:
            b[x-1] = a[i]
            
    print(col)

    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
        def dump(*args):
            names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
            print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
    except:
        def dump(*args):
            pass

    solve()

# vim: set foldmethod=marker:}}}

Submission status: Time Limit Exceeded

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

cnt = 0
while len(a) != 0:
    now = a.pop(0)
    now_i = 0
    while now_i < len(a):
        if a[now_i] > now:
            now = a.pop(now_i)
            continue
        now_i += 1
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
q = []
count = 1
cur_mx = -1
for i in range(n):
  inp = int(input())
  if inp > cur_mx:
    cur_mx = inp
  else:
    q.append(inp)
while len(q) > 0:
  tmp = []
  cur_mx = -1
  for x in q:
    if x > cur_mx:
      cur_mx = x
    else:
      tmp.append(x)
  q = tmp
  count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:

class UnionFind:
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)
        self.cnt = 0
 
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def groupsize(self):
        self.cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt
 
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

uf = UnionFind(N+1)
maxims = [A[0]]
ans = 1
for i in range(1,N):
    maxims.sort(reverse = True)
    for j,m in enumerate(maxims):
        if A[i] > m:
            maxims[j] = A[i]
            break
    else:
        maxims.append(A[i])
        ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

for i in range(N-1):
    A = int(input())

    if find[0] >= A:
        find.insert(0, A)
    else:
        idx = bisect.bisect_left(find, A)
        x = find.pop(idx-1)
        bisect.insort_left(find, A)

print(len(find))

Submission status: Time Limit Exceeded

Solution code:
def bi(l,x,m):
    ok = m
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x,m) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
        t.sort(reverse=True) 
print(m)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
q = []
count = 1
cur_mx = -1
for i in range(n):
  inp = int(input())
  if inp > cur_mx:
    cur_mx = inp
  else:
    q.append(inp)
while len(q) > 0:
  tmp = []
  cur_mx = -1
  for x in q:
    if x > cur_mx:
      cur_mx = x
    else:
      tmp.append(inp)
  q = tmp
  count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(input())

ans = 1
tops = [A[0]]
for i in range(1,N):
    if len(tops) > 1:
        tops.sort(reverse=True)

    for max_i in range(len(tops)):
        if tops[max_i] < A[i]:
            tops[max_i] = A[i]
            break
    else:
        tops.append(A[i])
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC134-E

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l1=[I() for _ in range(n)]

  l1.reverse()
  l2=[0]*n

  c=1

  # print(l1)
  for i,x in enumerate(l1):
    # print(l2)
    if l2[i]==0:
      l2[i]=i+1
    for j in range(i,n):
      y=l1[j]

      if c==n-1:
        return max(l2)

      if x>y and l2[j]==0:
        c+=1
        l2[j]=i+1
        x=y

      if l1[j]==0:
        break

  return max(l2)

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
l=[]
for i,x in enumerate(A):
    if 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))

Submission status: Time Limit Exceeded

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

counter = 1
maximum = [a[0]]

for i in range(1, n):
    x = -1
    y = None
    for j in range(len(maximum)):
        if a[i] > maximum[j] and maximum[j] > x:
            x = maximum[j]
            y = j

    if x == -1:
        counter += 1
        maximum.append(a[i])

    else:
        maximum[y] = a[i]

print(counter)

Submission status: Time Limit Exceeded

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

from heapq import *
from bisect import *

que = []

ans = 0
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        ans += 1
    else:
        idx = bisect_right(que, a-1)
        if idx == 0:
            insort_left(que, a)
            ans += 1
        else:
            b = que[idx-1]
            #if a != b:
            que[idx-1] = a
            #idx2 = bisect_right(que, a-1)

    # print(que, ans)
print(ans)

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
        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: #entryとdata(代入するデータ)を比較してentryの方が大きい場合
                    if n.left is None: #nの左エッジに何も入っていない場合
                        n.left = Node(data) #nの左エッジに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 = data
                    n = n.right #nの右エッジに何か入っている場合nにnのrightを代入
    def getAns(self) :
        return self.ans


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

tree = BST(A)

print(tree.getAns())