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 _ in range(N)]

count = 0
tmp = - 10 ** 10
for i in range(N):
    # print ('i', i)
    if A[i] == -10 ** 11:
        continue
    if tmp == -10 ** 10:
        tmp = A[i]
        count += 1
        for j in range(i + 1, N):
            if tmp < A[j]:
                tmp = A[j]
                A[j] = - 10  ** 11
            if j == N - 1:
                tmp = - 10 ** 10
# print (A)
print (count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = [-1]

# まずは全ての値を取ってくる
for i in range(N):
    # Aの値を取る
    swi = 0
    A = int(input())
    for j in range(len(A_list)):
        if A > A_list[j]:
            A_list[j] = A
            swi = 1
            break
    if swi == 0:
        A_list.append(A)


print(len(A_list))

Submission status: Time Limit Exceeded

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

color = 1
while True:
    now = -1
    d = []
    for i in range(len(A)):
        if A[i] > now:
            now = A[i]
            d.append(i)

    for i in range(len(d)):
        del A[d.pop()]
    if len(A) == 0:
        break
    color += 1

print(color)

Submission status: Time Limit Exceeded

Solution code:
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    a_list = [int(input()) for _ in range(n)]

    color_list = []

    for a in a_list:
        # 既存の色でぬれるかチェック
        can_draw = False
        # 増分が一番小さいものを選ぶ
        best_diff = 10 ** 9 + 1
        best_index = -1
        for index, color in enumerate(color_list):
            if color < a:
                can_draw = True
                diff = a - color
                if diff < best_diff:
                    best_diff = diff
                    best_index = index
        if can_draw:
            color_list[best_index] = a
        else:
            color_list.append(a)
        # print(color_list)
    # print()
    # print(color_list)
    print(len(color_list))

# a1から順番に塗っていく
# 色ごとに、今まで塗った最大値を記録する
# 既存の色でぬれる場合は、なるべく最大値の増分が少なくなるように色を選ぶ
# 既存の色でぬれない場合は新しい色を作って最大値を記録する

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

colors_tail = []
for a in A:
    for i, tail in enumerate(colors_tail):
        if tail < a:
            colors_tail[i] = a
            break
    else:
        heapq.heappush(colors_tail, a)

print(len(colors_tail))

Submission status: Time Limit Exceeded

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

col = [-1]

for ai in list_a:
    f = True
    for i,col_i in enumerate(col):
        if (col_i < ai):
            col[i] = ai
            f = False
            break
    
    if (f):
        col.append(ai)

print(len(col))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

print(len(alist))

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
nums = [int(input()) for i in range(n)]
count = 0
prevMaxs = []
for i in range(n):
    num = nums[i]
    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:
import sys, collections

def count(q, ans):
    unused = collections.deque()
    ans += 1
    num = -1
    while q:
        n = q.popleft()
        if n <= num:
            unused.append(n)
        else:
            num = n
    return unused, ans

def solve():
    input = sys.stdin.readline
    N = int(input())
    col = 0
    q = collections.deque()
    for _ in range(N):
        q.append(int(input()))

    while q:
        q, col = count(q, col)

    print(col)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    _ = int(input())
    A = list(map(int, sys.stdin.readlines()))
    
    arr = [A[0]]
    for a in A[1:]:
        if a <= arr[-1]:
            arr.append(a)
        else:
            for i in range(len(arr)):
                if a > arr[i]:
                    arr[i] = a
                    break
    print(len(arr))
    
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
n=int(input())
aa=[]
for i in range(n):
    aa.append(int(input()))
bb=[]
for i in range(n):
    if not bb:
        bb.append(aa[i])
    else:
        if bb[0] > aa[i]:
            bb.append(aa[i])
            bb = sorted(bb)
        else:
            for j in range(len(bb)):
                if bb[-(j+1)] < aa[i]:
                    bb[-(j+1)] = aa[i]
                    bb = sorted(bb)
                    break
            else:
                bb = [aa[i]] + bb
print(len(bb))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

next_add_i = 0
for i in range(N):
    A = int(input())

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

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

print(next_add_i)

Submission status: Time Limit Exceeded

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

ls = [A[0]]
num = 1
for a in A[1:]:
	new = True 
	for i in range(num):
		if ls[i] < a:
			new = False
			ls[i] = a
			break
	if new:
		num += 1
		ls.append(a)

print(len(ls))

Submission status: Time Limit Exceeded

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

ans = [A[0]]
for i in range(1, N):
    tmp = (-1, -1)
    for j in range(len(ans)):
        if ans[j] < A[i] and ans[j] > tmp[1]:
            tmp = (j, ans[j])

    if tmp[0] >= 0:
        ans[tmp[0]] = A[i]
    else:
        ans.append(A[i])

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
res = 0
while len(a) > 0:
    last = a[0]
    del a[0]
    res += 1
    i = 0
    while i < len(a):
        if last < a[i]:
            last = a[i]
            del a[i]
        else:
            i += 1
print(res)

Submission status: Time Limit Exceeded

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

check = [False for _ in range(N)]
cnt = 0
for i in range(N):
  if check[i] == False:
    cnt += 1
  for j in range(i + 1, N):
    if A[j] > A[i]:
      check[j] = True
      check[i] = True
print(cnt)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:

def bisect(a,A,lo,hi):
    if hi-lo==1:
        return hi
    if A[(hi+lo)//2]>=a:
        return bisect(a,A,(hi+lo)//2,hi)
    else:
        return bisect(a,A,lo,(hi+lo)//2)

N = int(input())

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

B = [A[0]]

for i in range(1,N):
    if B[-1]>=A[i]:
        B.append(A[i])
    else:
        if B[0]<A[i]:
            B[0]=A[i]
        else:
            B[bisect(A[i],B,0,len(B)-1)]=A[i]

print(len(B))

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())

max_list = [-1]

for i in range(N):
    ok_list = [x for x in max_list if x < A[i]]
    if ok_list:
        max_idx = max_list.index(sorted(ok_list)[-1])
        max_list[max_idx] = A[i]
    else:
        max_list.append(A[i])

ans = len(max_list)
print(ans)

Submission status: Time Limit Exceeded

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

d = {}
visited = []
for i in range(n):
    if i in visited:
        continue
    d.update({i:[i]})
    for j in range(i+1,n):
        if j not in visited and a[d[i][len(d[i])-1]] < a[j]:
            d[i].append(j)
            visited.append(j)
print(len(d))

Submission status: Time Limit Exceeded

Solution code:
import math

def search(A, S):

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



def main():
    N = int(input())
    A = [int(input())]
    le = 1
    for _ in range(N-1):
        S = int(input())
        A = search(A, S)
    print(len(A))

    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

colors_tail = []
for a in A:
    for i, tail in enumerate(colors_tail):
        if tail < a:
            colors_tail[i] = a
            break
    else:
        colors_tail.append(a)

print(len(colors_tail))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# print(top)

print(col)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
  x = [int(input()) for _ in range(int(input()))]
  c = [x[-1]]

  for i in range(len(x) - 2, -1, -1):
    j = bisect.bisect(c, x[i])

    if j == len(c):
      c.append(x[i])
    else:
      c = c[:j] + c[j + 1:]
      bisect.insort(c, x[i])

  print(len(c))


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

S = []

cnt = 0
for i in range(N):
    j = bisect.bisect_left(S, A[i])
    if j <= 0:
        cnt += 1
        S.insert(j, A[i])
    else:
        S[j-1] = A[i]

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for _ in range(N):
  A.append(int(input()))
  
num=0
while len(A)!=0:
    i=0
    temp=A.pop(0)
    while i<len(A):
        if temp<A[i]:
            temp=A.pop(i)
        else:
            i+=1
    num+=1
print(num)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


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


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    
    L = [A.pop(0)]
    ma = L[0]
    for a in A:
        if ma >= a:
            ma = a
            L.append(ma)
            continue
        for i, l in enumerate(L):
            if l < a:
                L[i] = a
                if l == ma:
                    ma = L[-1]
                break
        else:
            L.append(a)
    return len(L)


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))

    # N = 10**5
    # A = [random.randint(1, 10**9) for _ in range(N//2)]
    # A.sort()
    # A.reverse()
    # A += [random.randint(1, 10**9) for _ in range(N//2)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
sys.setrecursionlimit(4100000)
k = int(input())
a = [int(input()) for i in range(k)]
counter = 0
ans = 0
while counter < k:
    rank = []
    indexes = []
    for ind, n in enumerate(a):
        index = bisect.bisect_left(rank, n)
        if index == len(rank):
            rank.append(n)
            indexes.append(ind)
        else:
            rank[index] = n
    counter += len(rank)
    indc = 0
    for i in indexes:
        a.pop(i-indc)
        indc += 1
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [int(input()) for i in range(n)]
list = [-1]
count = 0
for i in s:
  flg = True
  for l in range(len(list)):
    if list[l] < i:
      list[l] = i
      flg = False
      break
  if flg:
    list.append(i)
    
print(len(list))

Submission status: Time Limit Exceeded

Solution code:
N=list(map(int, input().split()))
N=N[0]
color=[int(input())]
for i in range(1,N):
    num=int(input())
    flag=0
    for j in reversed(list(range(len(color)))):
        if color[j]<num:
            color[j]=num
            flag=1
            break
    if flag==0:
        color.append(num)
print(len(color))

Submission status: Time Limit Exceeded

Solution code:
import collections

def seek_color_index(new_value):
    update_value = -1
    update_index = -1
    for c in color_max_collrxtions:
        if(update_value <= color_max_collrxtions[c] and color_max_collrxtions[c] < new_value):
            update_value = color_max_collrxtions[c]
            update_index = c
    return update_index

def paint_color(i):
    values = color_max_collrxtions.values()
    min_value = min(values)
    if(A_list[i] <= min_value):
        color_max_collrxtions[len(color_max_collrxtions)] = A_list[i]
    else:
        update_index = seek_color_index(A_list[i])
        color_max_collrxtions[update_index] = A_list[i]

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

color_max_collrxtions = collections.Counter()
color_max_collrxtions[0] = A_list[0]
for i in range(1, N):
    paint_color(i)
    
print(len(color_max_collrxtions))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=[int(input()) for _ in range(n)]
ans=[-1]*(n+1)
num=1
ans[0]=arr[0]
for i in range(1,n):
  for j in range(num):
    if ans[j]<arr[i]:
      ans[j]=arr[i]
      break
  else:
    ans[num]=arr[i]
    num+=1
print(num)

Submission status: Time Limit Exceeded

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

n = 0
while len(A)>0:
    n+=1
    t = A[0]
    left = []
    for a in A[1:]:
        if a>t: t=a
        else: left.append(a)
    A = left

print(n)

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

import sys
input = sys.stdin.readline

def Solve():
    L=[]
    N=int(input())
    for i in range(N):
        L.append(int(input()))
    

    col=1
    K=[]
    for i,a in enumerate(L):
        if i==0:
            K.append(a)
            continue
        pos=bisect.bisect_left(K,a)
        if pos==0:
            col+=1
            K=[a]+K
        else:
            K[pos-1]=a

    return col



print(Solve())

Submission status: Time Limit Exceeded

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

remain = N
color = 0

while remain != 0:
        num = A[0]
        B = []
        remain -= 1
        for i in range(1, len(A)):
                if num >= A[i]:
                        B.append(A[i])
                else:
                        num = A[i]
                        remain -= 1
        
        color += 1
        A = B

print(color)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

for i in range(N-1):
    A = int(input())
    idx = bisect.bisect_left(find, A)

    if not idx:
        find.insert(0, A)
    else:
        find[idx-1] = A

print(len(find))

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
ans = 0
m = 0
while m!=N:
    ans+=1
    k = -1
    for i in range(N):
        if k<A[i]:
            k,A[i],m = A[i],-1,m+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import bisect

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

colors = [A[0]]
for a in A[1:]:
    i = bisect.bisect_left(colors, a)
    if i != 0:
        del colors[i - 1]
    bisect.insort_left(colors, a)

print(len(colors))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import sys

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

#print(n)
#print(a)
#print(b)
print(max+1)

Submission status: Time Limit Exceeded

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

for _  in range(N):
    data.append([int(input()), 0])

def check(ary):
    f = False
    for a in ary:
        if a[1] == 0:
            f = True
            break
    return f

count = 0
while check(data):
    tmp = -1

    for i in range(N):
        if data[i][1] == 0 and data[i][0] > tmp:
            data[i][1] = 1
            tmp = data[i][0]

    count += 1

print(count)

Submission status: Time Limit Exceeded

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


colors = deque()
colors.append(a[0])
for num in a[1:]:
    exchange = False
    for i in range(len(colors)):
        if num > colors[i]:
            colors[i] = num
            exchange = True
            break
    if not exchange:
        colors.append(num)
print(len(colors))

Submission status: Time Limit Exceeded

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

flag = True
count = 0
while flag:
    flag = False
    prev = -1
    count += 1
    for i, (a, visited) in enumerate(As):
        if visited:
            continue
        if prev < a:
            prev = a
            As[i][1] = True
        else:
            flag = True

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = [int(input()) for i in range(n)]
count = 0
prevMaxs = []
for i in range(n):
    num = nums[i]
    if len(prevMaxs) == 0 :
        prevMaxs.append(num)
    else:
        maxIndex = -1
        maxNum = -1
        for j in range((len(prevMaxs))):
            if prevMaxs[j] < num and maxNum < prevMaxs[j]:
                maxIndex = j
                maxNum = prevMaxs[j]
        if maxIndex == -1:
            prevMaxs.append(num)
        else:
            prevMaxs[maxIndex] = num
print(len(prevMaxs))

Submission status: Time Limit Exceeded

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

n = 0
visited = [False] * N
while True:
  l = -1
  for i in range(N):
    if not visited[i]:
      visited[i] = True
      l = A[i]
      break
  if l == -1:
    break
  r = -1
  for i in range(N):
    if not visited[i]:
      if l < A[i] and r < A[i]:
        visited[i] = True
        r = A[i]
  n += 1
print(n)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())

array = np.array([])


def insert_sorted(array, value):
    index = np.searchsorted(array, value)
    if index:
        array[index - 1] = value
    else:
        array = np.insert(array, index, value)
    return array


for i in range(N):
    n = int(input())
    array = insert_sorted(array, n)

print(len(array))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
ans = []
for i in a:
  if len(ans) == 0:
    ans.append(a[0])
    continue
  doAppend = True
  for idx,ii in enumerate(ans):
    if i > ii:
      doAppend = False
      ans[idx] = i
      break
  if doAppend:
    ans.append(i)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[int(input())]

for i in range(n-1):
    a=int(input())
    f=True
    for i in range(len(l)):
        if l[i]<a:
            l[i]=a
            f=False
            break
    if f:
        l.append(a)
print(len(l))

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):
  for j in range(len(ans)):
    if ans[j] < a[i]:
      ans[j] = a[i]
      break
  else:
    ans.append(a[i])

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


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


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    
    L = [A.pop(0)]
    ma = L[0]
    for a in A:
        if ma >= a:
            ma = a
            L.append(ma)
            continue
        for i, l in enumerate(L):
            if l < a:
                L[i] = a
                if l == ma:
                    ma = min(L)
                break
        else:
            L.append(a)
    return len(L)


def main():
    N = read_int()
    A = [read_int() for _ in range(N)]
    print(slv(N, A))

    # N = 10**5
    # A = [random.randint(1, 10**9) for _ in range(N//2)]
    # A.sort()
    # A.reverse()
    # A += [random.randint(1, 10**9) for _ in range(N//2)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    logger = []

    logger.append(A[0])

    for a in A[1:]:
        for i, l in enumerate(logger):
            if l < a:
                logger[i] = a
                break
        else:
            logger.append(a)

    print(len(logger))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

remain = N
color = 0

while len(A) != 0:
        num = A[0]
        B = []
        for i in range(1, len(A)):
                if num >= A[i]:
                        B.append(A[i])
                else:
                        num = A[i]
        
        color += 1
        A = B

print(color)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

for i in range(n - 1):
    t = int(input())
    ch = 0
    if t <= ans[-1]:
        ans.append(t)
    else:
        for j in range(len(ans)):
            if t > ans[j]:
                ans[j] = t
                ch += 1
                break

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N=list(map(int, input().split()))
N=N[0]
color=[int(input())]
for i in range(1,N):
    num=int(input())
    flag=0
    for j in range(len(color)):
        if color[j]<num:
            color[j]=num
            flag=1
            break
    if flag==0:
        color.append(num)
print(len(color))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(int(input())for i in range(N))
H = [float('inf'),A[0]]
for i in range(1,N):
    if A[i] <= H[-1]:
        H.append(A[i])
    else:
        for j in range(len(H)-1,-1,-1):
            if H[j] >= A[i]:
                H[j+1] = A[i]
                break
print(len(H)-1)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def main():
    n = input()
    aa = []
    xx = [-input()]
    for _ in xrange(n - 1):
        aa.append(-input())
    for a in aa:
        if a >= xx[-1]:
            xx.append(a)
        else:
            i = bisect.bisect_right(xx, a)
            if i == len(xx):
                i -= 1
            xx[i] = a
    print len(xx)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(int(input())for i in range(N))
H = [float('inf'),A[0]]
for i in range(1,N):
    if A[i] <= H[-1]:
        H.append(A[i])
    else:
        for j in range(len(H)-1,-1,-1):
            if H[j] >= A[i]:
                H[j+1] = A[i]
                break
print(len(H)-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

ans = 1
t = [0]*N
t[0] = A[0]
idx = 0

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[int(input()) for i in range(n)]
ans=0
i=0
while(i<n):
    if(l[i]==-1):
        i+=1
        continue
    k=i
    j=i+1
    if(j<n and l[j]!=-1):
        ans+=1
        while(j<n):
            if(l[k]<l[j]):
                l[k]=-1
                #ans+=1
                k=j
            j+=1
        l[k]=-1
    #print(*l)
    i+=1
if(l[-1]!=-1):
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

import sys

n = int(input())
a = []
for i in range(0,n):
	a.append(0)
for i in range(0,n):
	a[i]=int(input())
b = []
for i in range(0,n):
	b.append(0)
for i in range(0,n):
	for j in range(i+1,n):
		if(a[i]>=a[j]):
			b[i]+=1
max=0
for i in range(0,n):
	if(max<b[i]):
		max = b[i]

#print(n)
#print(a)
#print(b)
print(max+1)

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

  return max(l2)

# main()
print(main())