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: Wrong Answer

Solution code:
a=[]
b=int(input())
c=[]
i=0
y=0
s=0
while i<b:
    a.append(int(input()))
    i+=1
    
for x in a:
    if x==a[0]:
        c.append(x)
        s+=1
    else:
        if c[-1]>=x:
            c.append(x)
            s+=1
        else:
            c.insert(0,x)
        
print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
an = [0]*n
max_an = 0
for i in range(0,n):
    an[i] = int(input())
    if an[i] > max_an:
        max_an = an[i]

local_min = an[0]
cnt = 1
for i in range(1, n):
    if (an[i] <= an[i-1]) and (local_min >= an[i]):
        cnt += 1
        local_min = an[i]

print(cnt)

Submission status: Wrong Answer

Solution code:
def search(num):
    flag=True
    for i,v in enumerate(c):
        if v>=num:
            flag=False
            c[i-1]==num
            c.sort()
            return 0
    c[-1]=num
N=int(input())
c=[int(input())]
for _ in range(N-1):
    tmp=int(input())
    if min(c)<tmp:
        search(tmp)
    else:
        c.append(tmp)
        c.sort()
print(len(c))

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

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

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

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

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

Submission status: Wrong Answer

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

for i in range(1, n):
    ss = sorted(colors, reverse = True)
    for j in range(len(colors)):
        if a[i] > ss[j]:
            colors[colors.index(ss[j])] = a[i]
            break
    if ss == sorted(colors):
        colors.append(a[i])

print(len(colors))
print(colors)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for _ in range(N):
  A.append(int(input()))
color = 1
c_max = A[-1]
A.pop(-1)
for a in A[::-1]:
  if c_max <= a:
    c_max = a
    color+=1
print(color)

Submission status: Wrong Answer

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

print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
i=0
s=[]
while i!=n:
    s.append(int(input()))
    i+=1
i=0
ans=[0]
j=0
f=0
while i!=n:
    while j!=len(ans):
        if ans[j]<s[i]:
            ans[j]=s[i]
            f=1
            break
        j+=1
    if f==0:
        ans.append(s[i])
    f=0
    j=0
    i+=1
print(len(ans))

Submission status: Wrong Answer

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

ans = 1
seen = []
for a in A:
    lower = bisect.bisect_left(seen, a)
    bigger = len(seen) - bisect.bisect_right(seen, a)
    seen.append(a)
    if lower < bigger:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    n = int(input())
    a = [int(input()) for i in range(n)]
    
    if(sum(a) == 0):
        print(n)
        exit()
        
    jdglist = []
    jdglist.append(a[0])
    count = 1
    for buf in a[1:]:
        # print(jdglist, buf)
        
        for index, jdgnum in enumerate(jdglist):
            if jdgnum <= buf:
                jdglist[index] = buf
                break
        else:                    
            count += 1
            jdglist.append(buf)
            
    # print(jdglist,count)
    print(count)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
li = [0]*n
for i in range(n):
        li[i]=int(input())
cnt=1
cnt2=0
a=[-1]*n
a[0]=li[0]
for i in range(n-1):
        for j in range(cnt):
                if a[j]>=li[i+1]:
                        cnt2+=1
        if cnt2==cnt:
                cnt+=1
                a[cnt-1]=li[i+1]
        cnt2=0

ans=0
for i in range(n):
        if a[i]!=-1:
                ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[int(input()) for i in range(N)]
color=0
for i in range(N-1):
	if L[i]>=L[i+1]:
		color+=1
print(color+1 if len(set(L))==1 else color)

Submission status: Wrong Answer

Solution code:
import copy

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

for i in range(N):
	if i == 0:
		output.append(A[i])
	elif A[i] <= min_val:
		output.append(A[i])
		min_val = A[i]
	else:
		cls = 10000000000000000000000000
		for j in range(len(output)):
			if A[i] - output[j] < cls:
				cls = A[i] - output[j]
				plc = j
		output[j] = A[i]
		
print(len(output))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


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

    a = [-INF]

    def isOK(index, key):
        return a[index] < key

    def binary_search(key):
        ng = -1
        ok = len(a)

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok

    ans = 0
    for aval in A:
        ok = binary_search(aval)
        # print(a, a[ok])
        if a[ok] == -INF:
            ans += 1
        a.insert(ok, aval)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
m = (10**9)+1
c = 0
f = 0
b = []
for i in range(n):
	tmp = int(input())
	if m >= tmp:
		f = 0
		if len(b) > 0:
			for k in range(1,len(b)+1):
				if b[-k] >= tmp:
					c+=1
					m = tmp
					b.append(tmp)
					f = 1
					break
		else:
			c+=1
			m = tmp
			b.append(tmp)
			f = 1		
		if f == 0:
			m = tmp
	else:
		m = tmp
print(c)

Submission status: Wrong Answer

Solution code:
import sys
INPUT = sys.stdin.readline
#入力関数
def SORO_INT(): return int(INPUT())
def MULT_INT_LIST(): return list(map(int, INPUT().split()))
def MULT_INT_MAP(): return map(int, INPUT().split())
def SORO_STRING(): return INPUT()
def MULT_STRING(): return INPUT().split()
 
N = SORO_INT()
A = list([int(input()) for i in range(N)])
for t in range(1,N):
        if A[0]<A[t]:
            A[t] = 10**9
t = A.count(10**9)
print(N-t)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    n = int(input())
    a_list = []
    color_list = []
    for i in range(n):
        a = int(input())
        paint = False
        for idx, color in enumerate(reversed(color_list)):
            if a > color:
                color_list[idx] = a
                paint = True
                break
        if paint == False:
            color_list.append(a)

    print(len(color_list))

Submission status: Wrong Answer

Solution code:
import sys, math
from collections import deque

readline = sys.stdin.readline

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


heads = []

for a in A:
    if len(heads) == 0:
        heads.append(a)
    else:
        left = 0
        right = len(heads) - 1
        while left - 1 > right:
            mid = (left + right) // 2
            if a <= heads[mid]:
                left = mid - 1
            else:
                right = mid + 1

        if a > heads[left]:
            heads[left] = a
        elif a > heads[right]:
            heads[right] = a
        else:
            heads.append(a)

print(len(heads))

Submission status: Wrong Answer

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

count = 1
pque = []
heapq.heappush(pque, -1 * A[0])
for i in range(1, N):
    if -pque[0] < A[i]:
        heapq.heappop(pque)
        heapq.heappush(pque, -A[i])
    else:
        count += 1
        heapq.heappush(pque, -A[i])
    # print (pque)

for i in range(len(pque) - 1):
    if pque[i] > pque[i + 1]:
        count -= 1

print (count)

Submission status: Wrong Answer

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


que = []
heapify(que)
ans = 0
min_num = float("inf")
for i, a in enumerate(a_list):
    if i == 0:
        heappush(que, a)
        min_num = a
        ans += 1
    else:
        idx = bisect_right(que, a-1)
        #if a <= min_num:
        if idx == 0:
            heappush(que, a)
            ans += 1
            min_num = a
        else:
            # idx = bisect_right(que, a-1)
            que[idx-1] = a
            if idx -1 == 0:
                min_num = a
    #print(que, min_num)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())
max_a = int(input().strip())
c = 1
for i in range(N - 1):
  a = int(input().strip())
  if a <= max_a:
    c += 1
    max_a = a

print(c)

Submission status: Wrong Answer

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

ans = [a[0]]
count = 0
for i in range(1,n):
  #  print(a[i],ans[count],count)
    if a[i] > ans[count]:
        ans[count] = a[i]
    else:
        mi = min(ans)
   #     print(mi,ans.index(mi))
        if mi < a[i]:
            idx = ans.index(mi)
            ans[idx] = a[i]
            count = idx
        else:
            ans.append(a[i])
            count += 1
    print(ans)
print(len(ans))

Submission status: Wrong Answer

Solution code:
import bisect

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

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

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

Submission status: Wrong Answer

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


que = []
heapify(que)
ans = 0
min_num = float("inf")
for i, a in enumerate(a_list):
    if i == 0:
        que.append(a)
        min_num = a
        ans += 1
    else:
        # idx = bisect_right(que, a-1)
        if a <= min_num:
        # if idx == 0:
            heappush(que, a)
            ans += 1
            min_num = a
        else:
            idx = bisect_right(que, a-1)
            que[idx-1] = a
            if idx -1 == 0:
                min_num = a
    #print(que, min_num)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout

N=int(stdin.readline())
arr=[]
for __ in range(N):
    arr.append(int(stdin.readline()))
map={}
j=0
map[j]=[arr[0]]
for i in range(1,N):
    if(map[j][-1]<arr[i]):
        map[j].append(arr[i])
    else:
        j+=1
        map[j]=[arr[i]]
two=0
for i in range(0,len(map)):
    if(len(map[i])>1):
        two+=1
if(two==0):
    two=N-1
elif(two==N):
  two=0
stdout.write(str(two+1))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

N = int(input().strip())
As = [int(input().strip()) for _ in range(N)]
Ordered_Aset = sorted(set(As), key=As.index)
count = N + 1 - len(Ordered_Aset)

for former, latter in zip(Ordered_Aset[:-1], Ordered_Aset[1:]):
    if former > latter:
        count += 1
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

res = 0
m = 0
for i in range(n):
    x = l[n-1-i]
    if i == 0:
        m = x
        res += 1
        #print(n-1-i,m,res)
    else:
        if m <= x:
            m = x
            res += 1
            #print(n-1-i,m,res)
        elif l[n-1-i] == l[n-2-i]:
            res += 1
            #print(n-1-i,m,res)
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

# 逆から解く
# 自分より小さい値を、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: Wrong Answer

Solution code:
N = int(input())
A = [int(input())]
B=[None for n in range(N)]
B[0]=A[0]
L = 1
for n in range(1,N):
	b = int(input())
	L = len(A)
	t = L-1
	if A[-1] < b:
		for a in range(L):
			if A[a] <= b:
				t = a
				break
		A[t] = b
	else :
		A.append(b)
print(len(A))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys
import copy
import bisect
# input = sys.stdin.readline()
k = int(input())
a = [-int(input()) for i in range(k)]
dp = []
for num in a:
    bi = bisect.bisect_left(dp,num)
    if bi == len(dp) or num == dp[-1]:
        dp += num,
    else:
        dp[bi] = num
print(len(dp))

Submission status: Wrong Answer

Solution code:
N = int(input())

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

from collections import defaultdict
COLOR = defaultdict(lambda: 0)

for b in BALL:
    for i in range(b):
        if COLOR[i] < b:
            COLOR[i] = b
            break
            
#print(COLOR)
print(len(COLOR))

Submission status: Wrong Answer

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


ls = deque([A[0]])
for a in A[1:]:
	ind = bisect.bisect(ls,a)
	if ind == 0:
		ls.appendleft(a)
	else:
		ls[ind-1] = a

print(len(ls))

Submission status: Wrong Answer

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 = [aa[i]] + bb
        else:
            for j in range(len(bb)):
                if bb[-(j+1)] < aa[i]:
                    bb[-(j+1)] = aa[i]
                    bb = bb[:-(j+2)] + sorted(bb[-(j+1):])
                    break
print(len(bb))

Submission status: Wrong Answer

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

count = 0
for i in range(10**9 + 1):
    count += a.count(i)
    if a.count(i) > 0:
        ix = a.index(i)
        a = a[0:ix]

    if len(a)<1:
        break
print(count)

Submission status: Wrong Answer

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

temp = [A[0]]
mini = A[0]
from bisect import bisect_left
ans = 1
for a in A[1:]:
    if a > mini:
        index = bisect_left(temp,a) - 1#index - 1がaより小さい
        if index == 0:
            mini = a
        temp.insert(index,a)
        temp.pop(index)
    else:
        temp.insert(0,a)
        mini = a
        ans += 1
print(ans)

Submission status: Wrong Answer

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

c = 0
colored = [False for _ in range(N)]
for i in range(N):
    if colored[i]:
        continue
    a = A[i]
    colored[i] = True
    for j in range(i, N):
        if colored[j] or a>=A[j]:
            continue
        colored[j] = True
    c += 1

print(c)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

# 1 <= N <= 10^5
# 0 <= Ai <= 10^9
N = int(stdin.readline().rstrip())
A = [int(stdin.readline().rstrip()) for _ in range(N)]

ruiseki_max = [-INF]

for i in range(N):
    ruiseki_max.append(max(ruiseki_max[i], A[i]))


cnt = 0
for i in range(1, N):
    if ruiseki_max[i] >= ruiseki_max[i+1]:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
d={}
a=int(input())
d[a]=1
d_min=a
ans=1
for _ in range(n-1):
    a=int(input())
    if a<=d_min:
        d_min=a
        ans+=1
        if a not in d.keys():
            d[a]=1
        else:
            d[a]+=1
        continue
    for i in range(a,-1,-1):
        if i in d.keys():
            if i==d_min and d[d_min]==1:
                d_min=a
            d[i]-=1
            if a not in d.keys():
              d[a]=1
            else:
              d[a]+=1
            break
print(ans)

Submission status: Wrong Answer

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

num = 1
group_min = []
group_min.append(a[0])
for i in range(1, n):
    if a[i] > a[i - 1]:
        continue
    else:
        if len(group_min) == 1:
            num += 1
            group_min.append(a[i])
        else:
            if a[i] <= min(group_min[:-1]):
                num += 1
                group_min.append(a[i])
            else:
                continue
print(num)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import deque

fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = deque([A[0]])#常に小さい順にソートされている
surfMax = A[0]
surfMin = A[0]
color = 1
for n,a in enumerate(A):
    if n==0:
        continue
    if a<=surfMin:
        color += 1
        surface.appendleft(a)
        surfMin = a
    elif a>surfMax:
        surface[color-1] = a
        surfMax = a
    else:
        pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
        surface[pos] = a
        if pos==0:
            surfMin = a
print(color)

Submission status: Wrong Answer

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

ans = 1
mem = A[0]

for i in range(1,N) :
    if mem >= A[i] :
        mem = A[i]
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

setA = set(A)
countA = set()
for a in setA:
    countA.add(A.count(a))

ans = 1
maxa = A[0]
if len(A) > 1:
    for a in A[1:]:
            if a < maxa:
                ans += 1
                maxa = a

print(ans + max(countA)-1)

Submission status: Wrong Answer

Solution code:
import sys
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

from bisect import bisect_left, bisect_right  # 二分探索
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー

def main():
    N = i2n()
    A = ii2nn(N)
    B = [-1]
    for a in A:
        t = bisect_left(B, a)
        if t > 0:
            B[t-1] = a
        else:
            heappush(B, a)
            #B = [a] + B
    print(len(B))

main()

Submission status: Wrong Answer

Solution code:
import sys, math
from collections import deque

readline = sys.stdin.readline

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


heads = []

for a in A:
    if len(heads) <= 1:
        heads.append(a)
    else:
        left = 0
        right = len(heads) - 1
        while True:
            mid = (left + right) // 2
            if a <= heads[mid]:
                left = mid - 1
            else:
                right = mid + 1
            if left - 1 <= right:
                break
        if a > heads[left]:
            heads[left] = a
        else:
            heads.append(a)

print(len(heads))

Submission status: Wrong Answer

Solution code:
N = int(input())
mina = int(input())
colorbox = [mina] #各色の最大値
ans = 1
for i in range(N-1):
    colorbox.sort(reverse = True)
    a = int(input())
    if a <= mina:
        ans += 1
        colorbox.append(a)
        mina = a
    elif a <= colorbox[-1]:
        ans += 1
        colorbox.append(a)
    else:
        for j in range(ans):
            if a > j:
                colorbox[j] = a
                break
            

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
    a = int(input())
    As.append(a)

times = 0

while len(As) > 1:

    Bs = [i for i in As[1:] if As[0] >= i]
    As = Bs
    times += 1

print(times+1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n):
    x=int(input())
    a.append(x)
'''
b=[]
flag=0
sum=0
for i in range(n-1):
    if a[i+1]-a[i] > 0:
        if flag==0:
            flag=1
            sum+=1
    else:
        if flag==0:
            b.append(a[i])
        else:
            b.append(a[i+1])
print(sum)
print(b)
'''
def search(a):
    if a!=[]:
        b=[]
        flag=0
        sum=0
        for i in range(len(a)-1):
            if a[i+1]-a[i] > 0:
                if flag==0:
                    flag=1
                    sum+=1
            else:
                if flag==0:
                    b.append(a[i])
                    #sum+=1
                else:
                    b.append(a[i+1])
        if sum==0:
            return len(a)
        return sum + search(b)
    else:
        return 0

print(search(a))

Submission status: Wrong Answer

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

if N == 1:
    print(1)
    exit()

if A[0] < A[1]:
    ans = 1
    m = A[0]
    M = A[1]
elif A[0] >= A[1]:
    ans = 2
    m = A[1]
    M = A[0]

for a in A[2:]:
    if a <= m:
        ans += 1
        m = a
    elif M < a:
        M = a

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(input()) for _ in range(N)]
ans = 1
now = a[0]
for i in range(1,N):
    if now >= a[i]:
        ans += 1
        now = a[i]
print(ans)

Submission status: Wrong Answer

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

cnt = 0
while len(A) > 0:
  min_A = min(A)
  i = A.index(min_A)
  A.pop(i)
  cnt += 1
  while i < len(A):
    if A[i] > min_A:
      A.pop(i)
    else:
      i += 1
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ans = [a[0]]

for i in range(1, N):

    if  ans[len(ans) - 1] >= a[i]:
        ans.append(a[i])
    elif ans[0] < a[i]:
        ans[0] = a[i]
    elif ans[len(ans) - 2] >= a[i]:
        ans[len(ans) - 2] = a[i]
    else:
        l = 0
        h = len(ans) - 1
        m = (l + h) // 2
        while True:
            if ans[m] >= a[i]:
                l = m
                m = (l + h) // 2
                continue

            if ans[m - 1] < a[i]:
                h = m
                m = (l + h) // 2
                continue
            break
        ans[m] = a[i]

print(len(ans))

Submission status: Wrong Answer

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

col, maxCol, beforeV = 1, 1, A[0]

for i in range(1, N):
    if beforeV < A[i]:
        pass
    elif beforeV == A[i]:
        col += 1
        maxCol = max(maxCol, col)
    elif maxCol < 2:
        col += 1
        maxCol = max(maxCol, col)
        col = 1

    beforeV = A[i]

print(maxCol)

Submission status: Wrong Answer

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


def update_solution(sln, k):
    ln = len(sln)
    if ln == 0 or k <= sln[0]:
        sln.append(k)
        return

    for j in range(ln):
        if sln[ln - j - 1] < k:
            sln[ln - j - 1] = k
            break


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

print(len(sln))

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque

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


def colorfind(a, colors):
    index = bisect.bisect_left(colors, a)
    return index


color = deque([])
mincolor = 0
for i in range(n):
    if i == 0:
        color.appendleft(a[i])
        mincolor = a[i]
    elif mincolor >= a[i]:
        color.appendleft(a[i])
        mincolor = a[i]
    else:
        colorindex = colorfind(a[i], color)
        color[colorindex - 1] = a[i]

print(len(color))

Submission status: Wrong Answer

Solution code:
n = int(input())
an = [0]*n
max_an = 0
for i in range(0,n):
    an[i] = int(input())
    if an[i] > max_an:
        max_an = an[i]

local_min = max_an
cnt = 1
for i in range(1, n):
    if (an[i] <= an[i-1]) and (local_min >= an[i]):
        cnt += 1
        local_min = an[i]

print(cnt)

Submission status: Wrong Answer

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

n = 0
m = float("inf")
for i in range(N):
  if m >= A[i]:
    n += 1
  m = min(m, A[i])
print(n)

Submission status: Wrong Answer

Solution code:
import bisect

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

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

Submission status: Wrong Answer

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
        i = bisect.bisect_right(L, -a)
        L[i] = -a
        ma = L[-1]
        print(L, a)
    return len(L)



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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from copy import copy


def solve():
    N = int(input())
    A = []
    count = 0
    for _ in range(N):
        A.append(int(input()))
    while A:
        a = A.pop()
        count += 1
        B = []
        while A:
            b = A.pop()
            if b >= a:
                B.append(b)
            a = b
        A = B[::-1]
    return count
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

temp = [A[0]]
mini = A[0]
from bisect import bisect_left
ans = 1
for a in A[1:]:
    if a > mini:
        index = bisect_left(temp,a) - 1#index - 1がaより小さい
        temp.insert(index,a)
        temp.pop(index)
    else:
        temp.insert(0,a)
        mini = a
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush
n = int(input())
a = [int(input()) for _ in range(n)]

c = []
c.append(a[0])
for ai in a[1:]:
    for ci in range(len(c) - 1, -1, -1):
        if c[ci] < ai:
            c[ci] = ai
            break
    else:
        c.append(ai)

print(len(c))

Submission status: Wrong Answer

Solution code:
import sys
line = sys.stdin.readline
N = int(line())
a = [int(line()) for _ in range(N)]
x = [0] * N

count = 0
for i in range(N):
    if x[i] == 1:
        continue
    count += 1
    x[i] = 1
    prev = a[i]
    for j in range(i + 1, N):
        if a[j] > prev:
            x[j] = 1
            prev = x[j]

print(count)

Submission status: Wrong Answer

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

for i in range(n):
    A.append((int(input()),i))

old=1000000000000000000000000000000000
ans=0

A.sort()

for tup in A:
    if tup[1] < old or tup[0]==eld:
        ans+=1
    old=tup[1]
    eld=tup[0]
        
print(ans)