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: Runtime Error

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

def chop(As):
    res = []
    minibatch=[As[0]]
    for i in range(len(As)-1):
        if As[i]<As[i+1]:
            minibatch.append(As[i+1])
        else:
            res.append(minibatch)
            minibatch=[As[i+1]]
    if minibatch:
        res.append(minibatch)
    return res
    
chopped = chop(As)
remains = chopped

def kakutei(remains):
    deletes = []
    for i in range (1,len(remains)):
        if remains[0][-1]<remains[i][0]:
            remains[0].extend(remains[i])
            deletes.append(i)
    x = remains[0].copy()
    for d in deletes[::-1]:
        del remains[d]
    del remains[0]
    return (x,remains)
res = []
while remains:
    x, remains = kakutei(remains)
    res.append(x)
print(len(res))

#N 個の整数からなる数列 A={A1,A2,⋯,AN} が与えられます。 N 個それぞれの整数に対して、色を 1つ選んでその色を塗ります。 この時、以下の条件を満たす必要があります:
#Aiと Aj(i<j) が同じ色で塗られているならば Ai<Aj
#が成立する
#条件を満たすように色を塗る時、用いる色の数の最小値を求めてください。

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque

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

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

print(len(ans))

Submission status: Runtime Error

Solution code:
N = int(input())    
color_list =  [int(input())]
max_color = color_list[0]
color_list_size = 1

for i in range(N-1):
    new_value = int(input())
    if(new_value > max_color):
        color_list[0] = new_value
        max_color = new_value
    else:
        add_flag = True
        for i in range(1, color_list_size):
            if(new_value > color_list[i]):
                color_list[i] = new_value
                add_flag = False
                break
        if(add_flag):
            color_list += [new_value]
        color_list_size += 1
print(len(color_list))

Submission status: Runtime Error

Solution code:
n = input()
a = list(map(int, input().split()))
count = 0
min = a[0]
for i in range(n):
    if min > a[i]:
        min = a[i]
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[0]*n
min=[0]*0
max=[0]*0
for i in range(n):
    a[i]=int(input())
    if(i==0):
        min.append(a[0])
        continue
    if(a[i-1]>=a[i]):
        max.append(a[i-1])
        min.append(a[i])
        if(i==n-1):
            max.append(a[i])
    
#print(a)
#print(min)
#print(max)

for _ in range(n):
    for i in range(len(max)):
      owari=False
      for j in range(i):
         if(max[j]<min[i]):
                max[j]=max[i]
                max.pop(i)
                min.pop(i)
                owari=True
                break
    if(owari):break

#print(min)
#print(max)
print(len(max))

Submission status: Runtime Error

Solution code:
import bisect
 
 
N = int(input())
 
lis = []
 
A1 = int(input())
 
 
lis.append(A1)
 
 
for i in range(N-1):
 
    A = int(input())
 
    flag = True
    ins = bisect.bisect_left(lis,A)
 
    if ins == 0:
        B = [A] + lis
        lis = B.copy()
 
    if lis[ins-1] < A:
        lis[ins-1] = A
 
"""
    for l in lis:
 
 
 
        if l < A:
            l = A
            flag = False
            lis.sort()
            maxi = max(maxi , i)
            break
 
    if flag:
        lis.append(A)
"""
 
#print (lis)
print (len(lis))

Submission status: Runtime Error

Solution code:
import math




def search3(S):
    harf = int(len(A)/3)
    for i, a in enumerate(A[harf:]):
        if a < S:
            A[i] = S
            return 
    return

def search2(S):
    harf = int(len(A)/2)
    for i, a in enumerate(A[harf:]):
        if a < S:
            A[i] = S
            return 
    return

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



def main():
    N = int(input())
    A[0] = int(input())
    m = A[0]
    harf = 0
    for _ in range(N-1):
        S = int(input())
        if S <= m:
            A.append(S)
        elif S <= th:
            search3(S)
        elif S <= harf:
            search2(S)
        else:
            search(S)
        m = A[-1]
        harf = A[int(len(A)/2)]
        th = A[int(len(A)/3)]
    print(len(A))

    

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

Submission status: Runtime Error

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

cnt = 0
for _ in range(len(a)):
  if len(a) == 0:
    break
  a_max = max(a)
  a_i = a.index(a_max)
  d = [a_i]
  tmp = a_max
  for i in range(1, a_i + 1):
    if a[a_i - i] < tmp:
      tmp = a[a_i - i]
      d.append(a_i - i)
    else:
      break
  for di in d:
    del a[di]
  cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque
import heapq

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

# d = deque([A[0]])
lst = [A[0]]
# h = heapq.heapify([A[0]])

for a in A[1:]:
    lst.sort()
    if a <= lst[0]:
        lst.append(a)
    else:
        left = 0
        right = len(lst)
        mid = (left + right) % 2
        while left < right:
            mid = (left + right) % 2
            if a < lst[mid]:
                right = mid
            elif a > lst[mid]:
                left = mid + 1
            else:
                break
        lst[mid] = a

print(len(lst))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

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

B = []
min = -10000000000
for i in range(N):
	if min <= -A[i]:
		min = -A[i]
		B.append(-A[i])
	else:
		loc = bisect.bisect_right(B, -A[i])
		B[loc] = -A[i]

print(len(B))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
a_list = []
for i in range(N):
    a_list.append(int(input()))
color_counter = 0
for i in range(N):
    color_counter += 1
    compare_a = a_list.pop(0)
    for idx, ite in enumerate(a_list[:]):
        if compare_a < ite:
            compare_a = a_list.pop(idx)
    if len(a_list) == 0:
        break
print(color_counter)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
a_list = []
for i in range(N):
    a_list.append(int(input()))
color_counter = 0
while len(a_list) > 0:
    color_counter += 1
    compare_a = a_list.pop(0)
    for idx, ite in enumerate(a_list[:]):
        if compare_a < ite:
            compare_a = a_list.pop(idx)
    
print(color_counter)

Submission status: Runtime Error

Solution code:
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline

n = int(input())
#####単位元######
ide_ele = -1
#ide_ele = 10**9+1

#num:n以上の最小の2のべき乗
num =2**(n.bit_length())
seg=[ide_ele]*(2*num)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res
    
def main():
    used = defaultdict(int)
    a0 = int(input())
    tank = [a0]
    used[a0] = 1
    update(a0,a0)
    
    for i in range(1,n):
        a = int(input())
        while True:
            if used[tank[0]] > 0:
                break
            else:
                heapq.heappop(tank)
        #塗り替え
        if tank[0] < a:
            ma = query(0,a+1)

            used[ma] -= 1
            heapq.heappush(tank,a)
            used[a] += 1
            if used[ma] == 0:
                update(ma,-1)
        else:
            heapq.heappush(tank,a)
            used[a] += 1
        update(a,a)

    res = 0
    for e in tank:
        if used[e] > 0:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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.array(list(color).append(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: Runtime Error

Solution code:
N = int(input())
A = []
for i in range(N):
	a = int(input())
	if A == []:
		A.append(a)
	elif a <= min(A):
		A.append(a)
	else:
		A.sort().reverse()
		for x in A:
			if x < a:
				A.remove(x)
				A.append(a)
		
print(len(A))

Submission status: Runtime Error

Solution code:
N = int(input())
import bisect
a = []
for i in range(N):
    a.append(int(input()))
c = []
color = 0
for i in range(N):
    if(i == 0):
        c.append(a[0])
        color += 1
    else:
        if(a[i-1] < a[i]):
            c.append(a[i])
        elif(a[i-1] >= a[i]):
            if(min(c) >= a[i]):
                color += 1
                c.append(a[i])
                c = sorted(c)
            else:
                c[bisect.bisect_right(c,a[i])] = a[i]
print(color)

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque

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

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

print(len(ans))

Submission status: Runtime Error

Solution code:
N=int(input())

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

print(len(lasts)

Submission status: Runtime Error

Solution code:

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

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

Submission status: Runtime Error

Solution code:
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline

n = int(input())

#####単位元######
ide_ele = -1
#ide_ele = 10**9+1

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*(4*num)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res
    
def main():
    used = defaultdict(int)
    a0 = int(input())
    tank = [a0]
    used[a0] = 1
    update(a0,a0)
    
    for i in range(1,n):
        a = int(input())
        while True:
            if used[tank[0]] > 0:
                break
            else:
                heapq.heappop(tank)
        #塗り替え
        if tank[0] < a:
            ma = query(0,a+1)

            used[ma] -= 1
            heapq.heappush(tank,a)
            used[a] += 1
            if used[ma] == 0:
                update(ma,-1)
        else:
            heapq.heappush(tank,a)
            used[a] += 1
        update(a,a)

    res = 0
    for e in tank:
        if used[e] > 0:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect


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

    logger = [A[0]]

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

    print(len(logger))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline

n = int(input())

#####単位元######
ide_ele = -1
#ide_ele = 10**9+1

#num:n以上の最小の2のべき乗
num =2**(n.bit_length()+1)
seg=[ide_ele]*(2*num)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res
    
def main():
    used = defaultdict(int)
    a0 = int(input())
    tank = [a0]
    used[a0] = 1
    update(a0,a0)
    
    for i in range(1,n):
        a = int(input())
        while True:
            if used[tank[0]] > 0:
                break
            else:
                heapq.heappop(tank)
        #塗り替え
        if tank[0] < a:
            ma = query(0,a+1)

            used[ma] -= 1
            heapq.heappush(tank,a)
            used[a] += 1
            if used[ma] == 0:
                update(ma,-1)
        else:
            heapq.heappush(tank,a)
            used[a] += 1
        update(a,a)

    res = 0
    for e in tank:
        if used[e] > 0:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

count = 0
while data != []:
    tmp = -1

    pop_c = 0
    for i in range(N):

        if data == []:
            break

        if data[i - pop_c] > tmp:
            tmp = data[i - pop_c]
            data.pop(i - pop_c)
            pop_c += 1

    count += 1

print(count)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline

n = int(input())

#####単位元######
ide_ele = -1
#ide_ele = 10**9+1

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()+10
seg=[ide_ele]*(2*num)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res
    
def main():
    used = defaultdict(int)
    a0 = int(input())
    tank = [a0]
    used[a0] = 1
    update(a0,a0)
    
    for i in range(1,n):
        a = int(input())
        while True:
            if used[tank[0]] > 0:
                break
            else:
                heapq.heappop(tank)
        #塗り替え
        if tank[0] < a:
            ma = query(0,a+1)

            used[ma] -= 1
            heapq.heappush(tank,a)
            used[a] += 1
            if used[ma] == 0:
                update(ma,-1)
        else:
            heapq.heappush(tank,a)
            used[a] += 1
        update(a,a)

    res = 0
    for e in tank:
        if used[e] > 0:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())    
color_list = []
color_list.append(int(input()))
for i in range(N-1):
    new_value = int(input())
    if(new_value > color_list[0]):
        color_list[0] = new_value
    elif(new_value <= color_list[-1]):
        color_list += [new_value]
    else:
        bisect.insert(color_list, new_value)
print(len(color_list))

Submission status: Runtime Error

Solution code:
# 逆から解く
# 自分より小さい値を、None へ変えていく
cnt = 0
for i in range(N-1, -1, -1):
    if nums[i] is None:
        continue

    size = nums[i]
    nums[i] = None
    for j in range (i, -1, -1):
        if nums[j] is None:
            continue
        
        if nums[j] < size:
            nums[j] = None
    
    cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
class Levenshtein:
#ここで配列を立ち上げて、初期値を入れる
    def initArray(self,str1,str2):
        distance = []
        for i in range(len(str1)+1):
            distance.append([0]*(len(str2)+1))
            distance[i][0] = i
        for j in range(len(str2)+1):
            distance[0][j] = j
        return distance
#セルに値を入れる
    def editDist(self,str1,str2,distance):
        dist = [0]*3
        for i in range(1,len(str1)+1):
            for j in range(1,len(str2)+1):
                dist[0] = distance[i-1][j-1] if str1[i-1]==str2[j-1] else distance[i-1][j-1]+1
                dist[1] = distance[i][j-1]+1
                dist[2] = distance[i-1][j]+1
                distance[i][j]=min(dist)
        return distance[i][j]

    def __init__(self,str1,str2):
        self.str1 = str1
        self.str2 = str2
        Levenshtein.distance = self.initArray(str1,str2)
        Levenshtein.dist = self.editDist(str1,str2,Levenshtein.distance)
        
N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
A.append(0)
mini = []
hoge = []
for i in range(N):
  hoge.append(A[i])
  if A[i] >= A[i+1]:
    mini.append(A[i])
    hoge = []

#print(mini)
str1 = "".join(str(mini))
str2 = "".join(str(sorted(mini)))
#print(str1)
#print(str2)
colors = len(mini)
leven = Levenshtein(str1,str2)
#print(leven.dist)
colors = colors - (leven.dist/2) #レーベン
print(int(colors))

Submission status: Runtime Error

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

max_color = 1
cnt_color = 1
stack = []
stack.append(a[0])
p = 0

for i in range(1,n):
    if a[i-1] >= a[i]:
        if stack[p] < a[i]:
            cnt_color -= 1
            stack.remove(p)
            p -= 1
        else:
            cnt_color += 1
            stack.append(a[i])
            p += 1
            if cnt_color > max_color:
                max_color += 1

print(max_color)

Submission status: Runtime Error

Solution code:
import bisect

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

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

print(len(ans))

Submission status: Runtime Error

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

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

color = [a[n-1]]
color_max = a[n-1]

for i in range(1, n):
    i = n - i - 1
    if color_max <= a[i]:
        color.insert(bisect.bisect_left(color, a[i]), a[i])
        color_max = a[i]
    else:
        j = bisect.bisect_left(color, a[i])
        color[j] = a[i]
print(len(color))

Submission status: Runtime Error

Solution code:
# coding: utf-8


def pop_partial_a(A):
    target = A.pop(0)
    for i, a in enumerate(A[:]):
        if target < a:
            target = a
            A.pop(i)

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

    count = 0
    while A:
        count += 1
        pop_partial_a(A)
    print(count)

main()

Submission status: Runtime Error

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] = hoge
print(len(result))

Submission status: Runtime Error

Solution code:
def rec(a, res, before, stack):
    if len(a) == 0:
        return res
    if a[0] <= before:
        stack.append(a[0])
        return rec(a[1:], res+1, a[0], stack)
    else:
        return rec(a[1:], res, a[0], stack)

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

print(rec(a, 0, 0, []))

Submission status: Runtime Error

Solution code:
a=[int(input())for i in[0]*int(input())]
b=a[0]
d=1
for i in range(1,len(a)-1):
  if b>a[i]:d+=1;b=a[i]
  elif a[i]in a[i-1]:d+=1
print(d)

Submission status: Runtime Error

Solution code:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None


N = int(input())

A = [int(input()) for _ in range(N)]
A = sorted((v,i) for i,v in enumerate(A))

root = Node(None)

nodes = [None]*N
cur = root
for v,i in A:
    cur.next = Node(v)
    cur = cur.next
    cur.i = i
root = root.next

cur = root
while cur:
    nodes[cur.i] = cur
    cur = cur.next

cnt = 0
for n in nodes:
    if n.val is None:
        continue
    while n:
        prev = n
        cur = n.next
        v = n.val
        n.val = None
        while cur:
            if cur.i > n.i and cur.val > v:
                n = cur
                prev.next = cur.next
                break
            prev = cur
            cur = cur.next
        else:
            n = cur
    cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
import collections
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
c = collections.Counter(a)
print(c.most_common()[1])

Submission status: Runtime Error

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]]
    print(max_list, ok_list)
    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: Runtime Error

Solution code:
N = input()
N = int(N)
S = [int(input()) for _ in range(N)]
result = 0

while onon < N:
    result += 1
    hoge = S.pop(0)
    onon = 0
    for j in range(len(S)):
        if S[onon] > hoge:
            S.pop(onon)
        else:
            onon + 1
print(result)

Submission status: Runtime Error

Solution code:
#include<stdio.h>
#include<stdlib.h>
int main(){
    int n;
    scanf("%d",&n);
    int *arr=(int *)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)
    scanf("%d",arr+i);
    int ans=0;
    int i=0;
    int j;
    while(i<n){
        if(arr[i]==-1)
        {
            i+=1;
            continue;
        }
        int k=i;
        j=i+1;
        if(j<n && arr[j]!=-1){
            ans++;
            while(j<n){
                if(arr[k]<arr[j]){
                    arr[k]=-1;
                    k=j;
                }
                j+=1;
            }
            arr[k]=-1;
        }
        i++;
    }
    if(arr[n-1]!=-1)
    ans++;
    printf("%d",ans);
}
/*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
        #if(l[k])
        l[k]=-1
    i+=1
if(l[-1]!=-1):
    ans+=1
print(ans)*/

Submission status: Runtime Error

Solution code:
a=[int(input())for i in[0]*int(input())]
b=a[0]
k=0
d=1
for i in range(len(a)-1):
  if b>a[i]:d+=1;b=i
  elif a[i]in a[k:];d+=1
print(d)

Submission status: Runtime Error

Solution code:
def rec(a, res, before, stack):
    if len(a) == 1:
        if a[0] > stack:
            return res
        else:
            return res+1
    if a[0] <= before:
        return rec(a[1:], res+1, a[0], a[0])
    else:
        return rec(a[1:], res, a[0], stack)


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

# print(n)
# print(a)

res = rec(a, 1, 0, 0)

print(res)

Submission status: Runtime Error

Solution code:
import Control.Monad
import Data.List

main = do
    n <- read <$> getLine
    a <- map read <$> replicateM n getLine
    print $ length $ foldl' sub5 [] a

sub5 :: [Int] -> Int -> [Int]
sub5 ls n = if   null f
            then n:ls
            else n:delete (maximum f) ls
    where f = filter (<n) ls

Submission status: Runtime Error

Solution code:
from collections import deque
import bisect

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

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

print(len(colors))

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_left
n = int(input())
ans = deque([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: Runtime Error

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

ans = 0
while len(l) != 0:
    ln = l[:]
    temp = l[0]
    for i in range(1, len(l)):
        if l[i] > temp:
            temp = l[i]
            del ln[i]
    del ln[0]
    l = ln
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import sys
input=sys.stdin.readline
from collections import deque
N=int(input())

cnt=0
L=[]
for i in range(N):
    n=int(input())
    L.append(n)
#print(L)
Q=[-1,10**10]
Q=deque()
Q.appendleft(10**10)
Q.appendleft(-1)
#print(Q)
for i in range(N):
    if bisect.bisect_left(Q,L[i])==1:
        Q.insert(1,L[i])
    #elif bisect.bisect_left(Q,L[i])==len(Q)-1:
        #Q.insert(len(Q)-1,L[i])
    else:
        Q[bisect.bisect_left(Q,L[i])-1]=L[i]
#print(Q)
print(len(Q)-2)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000000000)
n=int(input())
a=[int(input()) for i in range(n)]
def func(ans):
    ans+=1
    now=a[0]
    a.remove(a[0])
    look=[]
    while len(a)>0:
        if a[0]<=now:
            look.append(a[0])
            a.remove(a[0])
        else:
            a.remove(a[0])
    if len(look)==0:
        return ans
    else:
        for i in range(len(look)):
            a.append(look[i])
        return func(ans)
print(func(0))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
lst = [10 ** 10]
print(lst)
for i in range(N):
	new_num = int(input())
	if new_num <= lst[0]:
		lst.insert(0,new_num)
		print(lst)
	else:
		j = 0
		while lst[j] <= new_num:
			j += 1
		lst[j - 1] = new_num
				
print(len(lst) - 1)