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
import bisect
input = sys.stdin.readline

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

class SortedList:
    def __init__(self):
        self.data = []
        
    def get(self, index):
        if len(self.data) <= index:
            return None
        return self.data[index]
    
    def insort(self, d):
        bisect.insort_left(self.data, d)
        
    def bisect_left(self, d):
        return bisect.bisect_left(self.data, d)
    
    def update(self, index, d):
        self.data[index] = d
        #self.data.sort()

d = SortedList()
d.insort(L[0])
for v in L[1:]:
    index = d.bisect_left(v)
    
    if d.get(index) == None:
        if d.data[index - 1] < v:
            d.update(index - 1, v)
        else:
            d.insort(v)
    elif d.data[index] < v:
        d.update(index, v)
    elif d.data[index - 1] < v:
        d.update(index - 1, v)
    else:
        d.insort(v)
        
print(len(d.data))

Submission status: Time Limit Exceeded

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

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

class SortedList:
    def __init__(self):
        self.data = []
        
    def get(self, index):
        if len(self.data) <= index:
            return None
        return self.data[index]
    
    def insort(self, d):
        bisect.insort_left(self.data, d)
        
    def bisect_left(self, d):
        return bisect.bisect_left(self.data, d)
    
    def update(self, index, d):
        self.data[index] = d
        # self.data.sort()

d = SortedList()
d.insort(L[0])
for v in L[1:]:
    index = d.bisect_left(v)
    
    if d.get(index) == None:
        if d.get(index - 1) < v:
            d.update(index - 1, v)
        else:
            d.insort(v)
    elif d.get(index) < v:
        d.update(index, v)
    elif d.get(index - 1) < v:
        d.update(index - 1, v)
    else:
        d.insort(v)
        
print(len(d.data))

Submission status: Time Limit Exceeded

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

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

class SortedList:
    def __init__(self):
        self.data = []
        
    def get(self, index):
        if len(self.data) <= index:
            return None
        return self.data[index]
    
    def insort(self, d):
        bisect.insort_left(self.data, d)
        
    def bisect_left(self, d):
        return bisect.bisect_left(self.data, d)
    
    def update(self, index, d):
        self.data[index] = d
        self.data.sort()
        
d = SortedList()
d.insort(L[0])
for v in L[1:]:
    index = d.bisect_left(v)
    
    if d.get(index) == None:
        if d.get(index - 1) < v:
            d.update(index - 1, v)
        else:
            d.insort(v)
    elif d.get(index) < v:
        d.update(index, v)
    elif d.get(index - 1) < v:
        d.update(index - 1, v)
    else:
        d.insort(v)
        
print(len(d.data))

Submission status: Time Limit Exceeded

Solution code:
def p_e():
    N = int(input())
    # A = [int(input()) for _ in range(N)]
    ans = [-1]

    for _ in range(N):
        a = int(input())
        is_set = False
        for i, l in enumerate(ans):
            if l < a:
                ans[i] = a
                is_set = True
                break

        if not is_set:
            ans.append(a)

    print(len(ans))


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

Solution code:
def p_e():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = [-1]

    for a in A:
        is_set = False
        for i, l in enumerate(ans):
            if l < a:
                ans[i] = a
                is_set = True
                break

        if not is_set:
            ans.append(a)

    print(len(ans))


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

Solution code:

def p_e():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = [[-1]]

    for a in A:
        is_set = False
        for l in ans:
            if l[-1] < a:
                l.append(a)
                is_set = True
                break

        if not is_set:
            ans.append([a])
            
    print(len(ans))


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

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

    while A:
        ans += 1
        stv = -1
        start = A.index(min(A))
        while start < len(A):
            if A[start] > stv:
                stv = A.pop(start)
            else:
                start += 1

    print(ans)


if __name__ == '__main__':
    p_e()

Submission status: Time Limit Exceeded

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

from bisect import bisect_left

def main():
  N = int(input())
  liA = list(map(int, [input() for _ in range(N)]))
  colors = [liA[0]]
  for a in liA[1:]:
    if a <= colors[0]:
      colors = [a] + colors
    else:
      i = bisect_left(colors, a)
      colors[i-1] = a

  print(len(colors))
  pass

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

from bisect import bisect_left

def main():
  N = int(input())
  liA = list(map(int, [input() for _ in range(N)]))
  colors = []
  for a in liA:
    i = bisect_left(colors, a)
    if i == 0:
      colors = [a] + colors
    else:
      colors[i-1] = a

  print(len(colors))
  pass

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list()

for i in range(0, N):
  A_i = int(input())
  A.append(A_i)

result_list = list()
result_list.append(A[0])

for i in range(1, len(A)):
  updated = False
  for j in range(0, len(result_list)):
    if A[i] > result_list[j]:
      result_list[j] = A[i]
      updated = True
      break
  
  if not updated:
    result_list.append(A[i])

color_num = len(result_list)
print(color_num)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

a=[0 for i in range(n)]
max=[]
for i in range(n):
    a[i]=int(input())
    if i>0 and a[i]<=a[i-1]:
        max.append(i)

count=0
for i in range(len(max)):
    for j in range(i,len(max)):
        if a[max[i]-1]<a[max[j]]:
            count+=1
print(len(max)-count+1)

Submission status: Time Limit Exceeded

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

color = [a[0]]
for i in range(1,n):
    color.sort(reverse=True)
    for j in range(len(color)):
        if color[j] < a[i]:
            color[j] = a[i]
            break
    else:
        color.append(a[i])

print(len(color))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
color_painted = [1]
color_used = 1
a_mins = {1 : a[-1], }
for i in range(n-2,-1,-1):
    if a_mins[color_used] <= a[i]:
        color_used = 0
        while color_used < len(color_painted):
            color_used += 1
            if a[i] < a_mins[color_used]:
                a_mins[color_used] = a[i]
                break
        else:
            color_used += 1
            a_mins[color_used] = a[i]
            color_painted.append(color_used)
    elif a[i] < a_mins[color_used]:
        a_mins[color_used] = a[i]

print(len(color_painted))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


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

    def update_or_insert(self, m):
        if m < self.n:
            if self.left:
                return self.left.update_or_insert(m)
            else:
                self.left = Node(m)
                return True
        else:
            if self.right:
                if self.right.left:
                    return self.right.update_or_insert(m)
                else:
                    if self.n < m <= self.right.n:
                        self.n = m
                        return False
                    else:
                        return self.right.update_or_insert(m)
            else:
                if self.n == m:
                    self.right = Node(m)
                    return True
                else:
                    self.n = m
                    return False


def main():
    n = get_int()
    A = gets(n, [int])
    root = Node(A[0])
    ans = 1
    for a in A[1:]:
        inserted = root.update_or_insert(a)
        if inserted:
            ans += 1
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right; from collections import Counter, defaultdict, deque, OrderedDict; from copy import deepcopy; from fractions import gcd; from functools import lru_cache, reduce; from math import ceil, floor; from sys import stdin, setrecursionlimit
import heapq as hq; import itertools as its; import operator as op


# globals
inf = float('inf')
input = stdin.readline


class Tree:
    def __init__(self, node):
        self.root = None


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

    def update_or_insert(self, m):
        pass


def main():
    n = get_int()
    A = gets(n, [int])
    largest = []
    for a in A:
        i = bisect_left(largest, a)
        if i > 0 and largest[i-1] != a:
            largest[i-1] = a
        elif i == len(largest) and i > 0 and largest[i-1] != a:
            largest[i-1] = a
        else:
            largest.insert(i, a)
    print(len(largest))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def gets(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    setrecursionlimit(4100000)
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
B = [10 ** 9 + 1]
for i in range(N):
  A = int(input())
  flag = True
  for j in range(len(B)):
    if A > B[j]:
      B[j] = A
      flag = False
      break
  if flag:
    B.append(A)
print(len(B) - 1)

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:
#!/usr/bin/env python3

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
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
from itertools import permutations
mod = 10**9 + 7

n = int(input())
a = [int(input()) for _ in range(n)]
dp = [0]*n
ans = 0
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if -a[j] <= -a[i]:
            dp[i] = max(dp[i],dp[j]+1)
    ans = max(ans,dp[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#E問題
from bisect import bisect_left

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

Submission status: Time Limit Exceeded

Solution code:
#E問題
import bisect

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

Submission status: Time Limit Exceeded

Solution code:
#E問題
import bisect

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

Submission status: Time Limit Exceeded

Solution code:
#E問題
import bisect

N = int(input())
A = [int(input()) for i in range(N)]
B = []
for i in range(N):
    if len(B) == 0:
        B.append(A[i])
    else:
        if B[0] >= A[i]:
            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:
#E問題
import bisect

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

Submission status: Time Limit Exceeded

Solution code:
#E問題
N = int(input())
A = [int(input()) for i in range(N)]
B = []
for i in range(N):
    if len(B) == 0:
        B.append(A[i])
    else:
        if B[0] >= A[i]:
            B.append(A[i])
        else:
            for j in range(len(B)):
                if B[j] >= A[i]:
                    B[j-1] = A[i]
                    break
    B.sort()
print(len(B))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = [int(input()) for x in range(N)]
ans_list = [[A_list[0]]]
for i in range(1, N):
    num = A_list[i]
    done = False
    for my_list in ans_list: 
        if my_list[-1] < num:
            my_list.append(num)
            done = True
            break
    if not done:
        ans_list.append([num])
    
    ans_list.sort(key = lambda x:x[-1], reverse=True)
#    print(ans_list)

print(len(ans_list))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
count = 0
b = set([])
num = set(list(range(n)))
for _ in range(n):
    a.append(int(input()))
while len(b) < n:
    temp_num = min(num - b)
    temp = a[temp_num]
    b.add(temp_num)
    temp_list = sorted(list(num - b))
    for temp_i in temp_list:
        if a[temp_i] > temp:
            temp = a[temp_i]
            b.add(temp_i)
    count += 1
print(count)

Submission status: Time Limit Exceeded

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

m=1
c[0]=a[0]

for i in range(1,n):
  f=0
  for j in range(m):
    if c[j]<a[i]:
      f=1
      c[j]=a[i]
      break
  if f==0:
    c[m]=a[i]
    m+=1

print(m)

Submission status: Time Limit Exceeded

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

N = int(input())

lasts = []

before = [int(input())]
lasts.append(before)

for _ in range(N - 1):
    current = int(input())
    if before[0] < current:
        before[0] = current
        continue
    try:
        low = next(x for x in lasts if x[0] < current)
        low[0] = current
    except StopIteration:
        lasts.append([current])

print(len(lasts))

Submission status: Time Limit Exceeded

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

N = int(input())

lasts = []

before = [int(input())]
lasts.append(before)

for _ in range(N - 1):
    current = int(input())
    if before[0] < current:
        before[0] = current
        continue
    lows = [x for x in lasts if x[0] < current]
    if len(lows) == 0:
        lasts.append([current])
    else:
        lows[0][0] = current

print(len(lasts))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
ans=1
p=[a[0]]
import bisect
for i in range(1,n):
    index = bisect.bisect_left(p,a[i]) 
    if index==0:
        ans+=1
        p.insert(index,a[i])
    else:
        p.insert(index,a[i])
        del p[index-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    temp = int(input())
    a.append(temp)
a.reverse()
b = [a[0]]
counter = 1
for i in range(1,n):
    temp = False
    for k in range(counter):
        if a[i] < b[k]:
            b[k] = a[i]
            temp = True
            break
    if temp == False:
        b.append(a[i])
        counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = []
from bisect import bisect_left
for _ in range(N):
    u = int(input())
    index = bisect_left(L,u)
    if index == 0:
        L = [u] + L
    else:
        L[index - 1] = u
print(len(L))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for i in [0]*n ]
# print(a)
s = set()
count = 0
c = -1
# for i in range(2):
while len(s)!=n:
	for i, t in enumerate(a) :
		# print(c)
		if i not in s:
			if c < t:
				c = t
				s.add(i)
		# print(t)
		# print(c)				
	count+=1
	# print(s)
	# print(count)
	c=-1
	
print(count)
# print(s)

Submission status: Time Limit Exceeded

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

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

for i in range(N-1):
  ai = int(input())
  flag = False
  for m in l:
    if max(m) < ai:
      m.append(ai)
      flag = True
      break
  if flag == False:
    l.append([ai])
    
print(len(l))

Submission status: Time Limit Exceeded

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

for ai in A:
  if l == []:
    l.append([ai])
    continue
    
  flag = False
  for m in l:
    if max(m) < ai:
      m.append(ai)
      flag = True
      break
  if flag == False:
    l.append([ai])
    
print(len(l))

Submission status: Time Limit Exceeded

Solution code:
a = int(input())

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

res = 0
while len(b) != 0:
    c = b.pop(0)
    temp = 0
    while temp < len(b):
        if b[temp] > c:
            c = b.pop(temp)
        else:
            temp += 1
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
table = []
for i in range(N):
    n = int(input())
    for t in table:
        if n - t[-1] > 0:
            t.append(n)
            break
    else:
        table.append([n])
print(len(table))

Submission status: Time Limit Exceeded

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

for i in a[1:]:
    lena=len(ans)
    for j in range(lena):
        if ans[j][-1]<i:
            ans[j]+=[i]
            break
        else:
            if j==lena-1:
                ans+=[[i]]

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(input()) for i in range(n)]
ans=[[a[0]]]
for i in a[1:]:
    ans.sort(key=lambda x:x[-1],reverse=True)
    for j in range(len(ans)):
        if ans[j][-1]<i:
            ans[j]+=[i]
            break
        else:
            if j==len(ans)-1:
                ans+=[[i]]

print(len(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#数列Aが与えられたとき、順番を変えずに小さい順の数列に分割する。このときの分割の最小を求める
def BS(A, x):
    if len(A) == 2:
        if A[1] < x:
            return 1
        else:
            return 0
    elif len(A) == 1:
        return 0
    half = len(A) // 2
    if x <= A[half]:
        return BS(A[:half], x)
    else:
        return BS(A[half:], x) + half

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
B = [A[0]] #小さい順
for i in range(1, N):
    #i += 1
    if A[i] <= B[0]:
        B = [A[i]] + B
    else:
        B[BS(B, A[i])] = A[i]
print(len(B))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())

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

colors = []

for i in range(N):
    target = bisect.bisect_left(colors, A[i])

    if target == 0:
        colors.insert(0, A[i])
    else:
        colors[target-1] = A[i]

print(len(colors))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop,heappush
n = int(input())
a = [-int(input()) for i in range(n)]
x = [a[0]]
for i in range(1,n):
    if max(x)<=a[i]:
        heappush(x,a[i])
    else:
        p = heappop(x)
        y = [p]
        while p<=a[i]:
            p = heappop(x)
            y.append(p)
        heappush(x,a[i])
        for i in range(len(y)-1): heappush(x,y[i])
print(len(x))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = int(input())
c = [a]
c_len = 1
for i in range(1, n):
    a = int(input())
    for j in range(c_len):
        if c[j] < a:
            c[j] = a
            break
    else:
        c.append(a)
        c_len += 1
    c.sort(reverse=True)
print(c_len)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=int(input())
ans=[]
for _ in range(N):
    num=int(input())
    
    index=bisect.bisect_left(ans,num)
    if index==0:
        tmp=[num]
        tmp.extend(ans)
        ans=tmp
    else:
        ans[index-1]=num
print(len(ans))

Submission status: Time Limit Exceeded

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

# a = [2, 1, 4, 5, 3]
# m = len(a)

cs = [0]*m
c_maxs = [a[0]]
minimum = a[0]
maximum = a[0]

for i in range(1, m):
  cont = False
  
  if a[i] <= minimum:
    cont = False
    minimum = a[i]
  elif maximum < a[i]:
    cont = True
    cs[i] = len(c_maxs)-1
    c_maxs[-1] = a[i]
    maximum = a[i]
  else:
    for c, c_max in enumerate(c_maxs):
      if c_max < a[i]:
        cs[i] = c
        c_maxs[c] = a[i]
        cont = True
        break
  
  if not cont:
    cs[i] = len(c_maxs)
    c_maxs.append(a[i])

# print(cs)
print(len(c_maxs))

Submission status: Time Limit Exceeded

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

cs = [0]*m
c_maxs = [a[0]]

for i in range(1, m):
  cont = False
  for c, c_max in enumerate(c_maxs):
    if c_max < a[i]:
      cs[i] = c
      c_maxs[c] = a[i]
      cont = True
      break
  
  if not cont:
    cs[i] = len(c_maxs)
    c_maxs.append(a[i])

print(len(c_maxs))

Submission status: Time Limit Exceeded

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

ans = 1
X = [-1]
for i in range(N):
    for j in range(ans):
        if X[j] < A[i]:
            X[j] = A[i]
            break
        elif j == ans - 1:
            X.append(A[i])
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

ans = 1
X = [-1]
for i in range(N):
    for j in range(ans):
        if X[j] < A[i]:
            X[j] = A[i]
            break
        elif j == ans - 1:
            X.append(X[ans-1])
            for k in range(ans-1,0,-1):
                X[k] = X[k-1]
            ans += 1
            X[0] = A[i]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())
A = [0] * N

# reverse
for i in range(N):
  A[- i - 1] = int(input().strip())

B = [A[0]]
for i in range(1, N):
  a = A[i]

  if a >= B[-1]:
    B.append(a)
  else:
    for j in range(len(B)):
      if a < B[j]:
        B[j] = a
        break

print(len(B))

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())
A = [0] * N

# reverse
for i in range(N):
  A[-1 - i] = int(input().strip())

B = [A[0]]
for i in range(1, N):
  a = A[i]

  if a >= B[-1]:
    B.append(a)
  else:
    for j in range(len(B)):
      if a < B[j]:
        B[j] = a
        break

print(len(B))

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())
A = [0] * N

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

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

print(len(B))

Submission status: Time Limit Exceeded

Solution code:
#数列Aが与えられたとき、順番を変えずに小さい順の数列に分割する。このときの分割の最小を求める
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
B = [A[0]] #大きい順
for i in range(N - 1):
    i += 1
    if B[-1] >= A[i]:
        B.append(A[i])
    else:
        for j in range(len(B)):
            if B[j] < A[i]:
                B[j] = A[i]
                break
print(len(B))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = []

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

color_base = []

for i, a in enumerate(A):
    for j, color in enumerate(color_base):
        if a > color :
            color_base[j] = a
            break
    else :
        color_base.append(a)

print(len(color_base))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a = [- int(input()) for i in range(n)]
tmp = [a[0]]
for i in range(1,n):
  if a[i] >= max(tmp):
    tmp.append(a[i])
  else:
    index=bisect.bisect_right(tmp,a[i])
    tmp[index] =a[i]
print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import sys
n = int(input())
tmp=[int(input())]
if n == 1:
  print(1)
  sys.exit()
for i in range(n-1):
  a = int(input())
  idx = bisect_left(tmp,a)
  if idx==0:
    tmp.insert(0,a)
  else:
    tmp[idx-1] =a
print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
import bisect,sys
n = int(input())
A = [int(input()) for i in range(n)]
tmp = [A[0]]
if n == 1:
  print(1)
  sys.exit()
for a in A[1:]:
  idx = bisect.bisect_left(tmp,a)
  if idx==0:
    tmp.insert(0,a)
  else:
    tmp[idx-1] =a
print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
import bisect,sys
n = int(input())
A = [int(input()) for i in range(n)]
tmp = [A[0]]
if n == 1:
  print(1)
  sys.exit()
for a in A[1:]:
  if a <= min(tmp):
    tmp.insert(0,a)
  else:
    tmp[bisect.bisect_left(tmp,a)-1] =a
print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a = [int(input()) for i in range(n)]
tmp = [a[0]]
for i in range(1,n):
  if a[i] <= min(tmp):
    tmp.insert(0,a[i])
  else:
    index=bisect.bisect_left(tmp,a[i])
    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)]
tmp = [a[0]]
for i in range(1,n):
  if a[i] <= min(tmp):
    tmp.append(a[i])
    tmp=sorted(tmp,reverse=True)
  else:
    index=bisect.bisect_left(tmp,a[i])
    tmp.insert(index,a[i])
    del tmp[index-1]
print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
tmp = [a[0]]
for i in range(1,n):
  if a[i] <= min(tmp):
    tmp.append(a[i])
    tmp=sorted(tmp,reverse=True)
  else:
    for j in range(len(tmp)):
      if a[i]>tmp[j]:
        tmp[j]=a[i]
        break
print(len(tmp))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

colors = []
colors.append(a_list[0])
for i in range(1, N):
    a = a_list[i]
    idx = bisect.bisect_left(colors, a)
    if idx == 0:
        colors.insert(0, a)
    else:
        colors[idx-1] = a

print(len(colors))