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:
import heapq
from collections import defaultdict
import sys
import bisect
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)
    aa = [int(input()) for i in range(n)]
    b = sorted(aa)
    for i in range(n):
        aa[i] = bisect.bisect_left(b,aa[i])
        
    
    a0 = aa[0]
    tank = [a0]
    used[a0] = 1
    update(a0,a0)
    
    for i in range(1,n):
        a = aa[i]
        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: Wrong Answer

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

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

color = [a[0]]
color_min = a[0]

for i in range(1, n):
    if color_min > a[i]:
        bisect.insort_left(color, a[i])
        color_min = a[i]
    else:
        j = bisect.bisect_left(color, a[i])
        color[j-1] = a[i]

print(len(color))

Submission status: Wrong Answer

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

import sys
input = sys.stdin.readline

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 = [i for i, x in enumerate(max_list) if x < A[i]]
    if ok_list:
        max_list[ok_list[0]] = A[i]
    else:
        max_list.append(A[i])

ans = len(max_list)
print(ans)

Submission status: Wrong Answer

Solution code:
#coding : utf-8

import os
import sys

class Color:
	def __init__(self, v):
		self.start = v
		self.maxv = v

def get_min(colors):
	return min(colors, key = lambda x: x.start).start

def get_max_index(colors):
	maxv = max(colors, key = lambda x: x.maxv).maxv
	
	for i, c in enumerate(colors):
		if colors[i].maxv == maxv:
			return i

N = int(input())

A = []

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

#print(N)
#print(A)

colors = [Color(A[0])]

for i in range(1, N):
	v = A[i]

	minv = get_min(colors)
	
	if v <= minv:
		colors.append(Color(v))

	else:
		idx = get_max_index(colors)
		colors[idx].maxv = v

print(len(colors))

Submission status: Wrong Answer

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

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

r = [-1]
count = 0
for a in A:
    b = bisect.bisect_right(r, a)
    if r[b-1] != a and r[b-1] < a:
            r[b-1] = a
            r.sort()
    else:
        r.insert(b, a)
print(len(r))

Submission status: Wrong Answer

Solution code:
import numpy as np
  
N = int(input())  
A = np.zeros(N)

for i in range(N):
    A[i] = int(input())
    
ans = 1
mi = A[0]

for i in np.arange(N-1) +1:
    if mi >= A[i]:
        ans += 1
        mi = A[i]
        
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import perm
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

########

N = i_inpl()
A = line_inpl(N)

tmp = INF
ans = 1
mv, s_mv = -1, INF
for i in range(N):
    if A[i] <= mv:
        if A[i] > s_mv:
            ans -= 1
        s_mv = mv
        mv = A[i]
        ans += 1
    else:
        mv = A[i]

print(ans)

Submission status: Wrong Answer

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

for i in range(n):
    if i == 0:
        l.append([a[i]])
    for j in range(len(l)):
        if l[j][-1] < a[i]:
            l[j].append(a[i])
            break
    else:
        l.append([a[i]])
print(len(l))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,math,heapq as hq
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())
aa = []
co = 0
ccc = 0
for i in range(1,n):
	if a[i] <= a[i-1]:
		if ccc != a[i-1]:
			aa.append([a[i-1],ccc])
			ccc = 0
		else:
			aa.append([a[i-1],0])
	else:
		if c == 0:
			ccc = a[i-1]
		c += 1
if ccc != a[-1]:
	aa.append([a[-1],ccc])
else:
	aa.append([a[-1],0])


d = cl.deque()
d.append(aa[0])
if aa[0][1] == 0:
	co += 1
for i in range(1,len(aa)):
	for j in range(len(d)):
		if d[j][0] < aa[i][0] and (d[j][0] < aa[i][1] or aa[i][1] == 0):
			d.popleft()
			d.append(aa[i])
			break
	else:
		co += 1
		d.append(aa[i])
print(co)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(input()) for i in range(n)]
color = [0]*(n+1)
cnt = 0
M = A[0]
for i in range(1,n):
    if M>=A[i]:
        M = A[i]
        cnt += 1
if M == A[0]:
    cnt += 1
print(cnt)

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)

before = deque([])
cnt = 1
for i in range(N-1):
    if A[i] >= A[i+1]:
        before.append(A[i])
        cnt += 1
    
    if len(before) != 0:
        num = before[-1]
        if num < A[i+1]:
            before.pop()
            cnt -= 1

if before:
    cnt += len(before)
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
cnt = 1
last = -1
num = []
for _ in range(int(input())):
    num.append(int(input()))

color = [num[0]]

for i in range(len(num)-1):
    if(min(color) >= num[i+1]):
        color.append(num[i+1])
    else:
        color[np.argmax(color)] = num[i+1]
print(len(color))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
ans_head=[-1]
for i in range(n):
  a=int(input())
  if min(ans_head)>=a:
    ans_head=[a]+ans_head

  #print(ans_head)
print(len(ans_head))

Submission status: Wrong Answer

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

B = [A[0]]
min_b = B[0]
for i in range(1, N):
    a = A[i]
    if a <= min_b:
        B.append(a)
        min_b = a

# print(B)
print(len(B))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import bisect

# いっこ入力
n =int(input())

# n行の数をリストへ
a = [int(input()) for i in range(n)] 

# color
c = [a[0]]

for i in range(1,n):
    if c[0] >= a[i]:
        c.insert(0,a[i])
    else:
        p = bisect.bisect_right(c, a[i])
        c[p-1]=a[i]
#        c.sort()

print(len(c))

Submission status: Wrong Answer

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

B=[0 for i in range(n)]
mm = max(A)+2
for i in range(n):
    if A[i]<=mm:
        B[i]+=1
        mm=i
    else:
        t=i
        while B[t]==0:
            t-=1
        B[t]-=1
        B[i]+=1
        #print(B)
        if mm==t and B[t]==0:
            while B[mm]==0:
                mm+=1
print(sum(B))

Submission status: Wrong Answer

Solution code:
def solve():
    n = int(input())
    A = [int(input()) for _ in range(n)]
    if len(set(A)) == 1:
        return n
    A.reverse()
    last = A[0]
    cnt = 0
    for a in A[1:]:
        if last <= a:
            cnt += 1
        last = a
    return cnt
print(solve())

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque
import sys
#import bisect
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]

def bisect(ls,x):
    l,r=0,len(ls)-1
    while r-l>1:
        mid=(l+r)//2
        if ls[mid]>=x: # condition
            l=mid
        else:
            r=mid
    #print('bisect',ls,x,'=',r)
    return r

n=I()
a=deque()
q=[[] for _ in range(n)]
m=0 # num of queue now
for i in range(n):
    a+=[I()]
#print('a=',a)

q=deque()
q.append(a.popleft())
#print(q,'q[',0,']=')

while a:
    c=a.popleft()
    if c<=q[0]:
        q.appendleft(c)
        #print(q,'q[',0,']=',c)
    else:
        i=bisect(q,c)
        q[i]=c
        #print(q,'q[',i,']=',c)


ans=len(q)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,math,heapq as hq
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())
aa = []
co = 0
ccc = 0
for i in range(1,n):
	if a[i] <= a[i-1]:
		if ccc != a[i-1]:
			aa.append([a[i-1],ccc])
			ccc = 0
		else:
			aa.append([a[i-1],0])
	else:
		if c == 0:
			ccc = a[i-1]
		c += 1
if ccc != a[-1]:
	aa.append([a[-1],ccc])
else:
	aa.append([a[-1],0])


d = cl.deque()
d.append(aa[0])
if aa[0][1] == 0:
	co += 1
for i in range(1,len(aa)):
	for j in range(len(d)):
		if d[j][0] <= aa[i][0] and (d[j][0] < aa[i][1] or aa[i][1] == 0):
			d.popleft()
			d.append(aa[i])
			break
	else:
		co += 1
		d.append(aa[i])
print(co)

Submission status: Wrong Answer

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

l=len(A)
Ans=1
a=A[0]

for i in range(1,l):
    if A[i]<=a:
        Ans+=1

print(Ans)

Submission status: Wrong Answer

Solution code:

import bisect

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

    colors = []

    t = int(input())
    colors.append(t)

    for i in range(n - 1):
        t = int(input())
        idx = bisect.bisect(colors, t)

        if idx == 0:
            colors.insert(idx, t)
        elif colors[idx - 1] == t:
            colors.insert(idx, t)
        else:
            del colors[idx - 1]
            colors.insert(idx - 1, t)

    print(len(colors))

if __name__ == '__main__':
    submit()

Submission status: Wrong Answer

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

ans = 1
mi = A[0]
for a in A[1:]:
    if a <= mi:
        ans += 1
        mi = a

print(ans)

Submission status: Wrong Answer

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

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

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

r = [-1]
count = 0
for a in A:
    b = bisect.bisect_right(r, a)
    if r[b-1] != a and r[b-1] < a:
            r[b-1] = a
    else:
        r.insert(b, a)
print(len(r))

Submission status: Wrong Answer

Solution code:
import sys
import math

input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]
ans = [[0,0]]
for i in range(N):
    flag = 1
    for array in ans:
        if array[len(array)-1] < A[i]:
            array.append(A[i])
            flag = 0
            break
    if flag == 1:
        ans.append([0,A[i]])
print(len(ans))

Submission status: Wrong Answer

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

lis = [[A[0], A[0]]]
tmp = A[0]
for i in range(1,N):
    lis[-1][1] = tmp
    if A[i] <= tmp:
        lis.append([A[i], A[i]])
    tmp = A[i]
lis[-1][1] = tmp
lis.sort(reverse=True)

ans = 0
used = [False] * len(lis)
tree = {}
while lis:
    l,r = lis.pop()
    tmp = []
    for k,lst in tree.items():
        for v in lst:
            if l > v:
                tmp.append([k,v])
    if tmp == []:
        if l not in tree:
            tree[l] = [r]
        else:
            tree[l].append(r)
    else:
        a,b = tmp.pop()
        tree[a][tree[a].index(b)] = r

print(sum(len(lst) for lst in tree.values()))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    c = 0
    for i in range(N - 2):
        if A[i] >= A[i + 1] >= A[i + 2]:
            c += 2
            continue
        if A[i] < A[i + 1] < A[i + 2]:
            continue
        if A[i] < A[i + 1] >= A[i + 2] or A[i] >= A[i + 1] < A[i + 2]:
            c += 1
            continue
    print(c)


main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect
N = int(input())
A = []

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

l = deque([])

for i in range(N):
    if l == []:
        l.append(A[i])
    else:
        index = bisect.bisect_right(l, A[i])
        index2 = bisect.bisect_left(l, A[i])
        if index == 0:
            l.appendleft(A[i])
        elif index != index2:
            if index2 == 0:
                l.appendleft(A[i])
            else:
                l[index-1] = A[i]
        else:
            l[index-1] = A[i]

print(len(l))

Submission status: Wrong Answer

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
    def ope(self, x, y):
        return x + y
    def update(self, i, v):
        while i <= self.n:
            self.data[i] = self.ope(self.data[i], v)
            i += i & -i
    def query(self, i):
        ret = 0
        while 0 < i:
            ret = self.ope(self.data[i], ret)
            i &= i - 1
        return ret
    def lower(self, w):
        if w <= 0:
            return 0
        x = 0
        k = 2**(self.n.bit_length())
        while k:
            if x + k <= self.n and  self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k >>= 1
        return x + 1



n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(list(set(a)))
d = {}
for i, j in enumerate(b):
    d[j] = i
a = [d[i] for i in a]
k = len(d)

B = BIT(k)
ans = 0
for i in a:
    i = i+1
    q = B.query(i)
    if q == 0:
        B.update(i, 1)
        ans += 1
    else:
        v = B.lower(q)
        if v != i:
            B.update(v, -1)
            B.update(i, 1)
        else:
            w = B.query(i-1)
            if w == 0:
                B.update(i, 1)
                ans += 1
            else:
                v = B.lower(q)
                B.update(v, -1)
                B.update(i, 1)
print(ans)

Submission status: Wrong Answer

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

B = [A[0]]
min_b = B[0]
for i in range(1, N):
    a = A[i]
    if a <= min_b:
        B.append(a)

# print(B)
print(len(B))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
l = [int(input()) for i in range(n)]
a = np.array([0]+ l)
diff = np.diff(a)
ans = 0
if (a>0).sum() == n:
  print(1)
else:  
  for i in range(n):
    if diff[i] <= 0 and ans < 2:
      ans += 1
    elif diff[i] <= 0 and diff[i-1]<=0:
      ans += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(input()) for i in range(n)]
color=0
sorta=sorted(a)
if sorta[0]==sorta[n-1]:
    print(n)
else:
    for i in range(n):
        if a[i]<=sorta[i]+i:
            color+=1
    print(color)

Submission status: Wrong Answer

Solution code:
n = int(input())
colors = []
colors.append(int(input()))
for i in range(1, n):
  a = int(input())
  if a <= min(colors):
    colors.append(a)
  else:
    colors[colors.index(min(colors))] = a
print(len(colors))

Submission status: Wrong Answer

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

from operator import itemgetter
from bisect import bisect_left

A.sort(key = itemgetter(1),reverse=True)
A.sort(key = itemgetter(0))

check = [False]*n
ans = 0
for a in A:
    value,index = a
    if not(check[index]):
        ans += 1
        for i in range(index,n):
            if check[i]:
                break
            check[i] = True
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(input()) for i in range(n)]
ct=0
for i in range(1,n):
  if a[i-1]>=a[i]:
    ct+=1
print(ct)

Submission status: Wrong Answer

Solution code:
from heapq import *

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

h = []
for a in A:
    if h:
        x = -heappop(h)
        if a >= x:
            heappush(h, -x)
    heappush(h, -a)


print(len(h))

Submission status: Wrong Answer

Solution code:
print(1)

Submission status: Wrong Answer

Solution code:
N = int(input())

colors = []
new_a = int(input())
colors.append([new_a, new_a])
global_min = new_a
for i in range(N-1):
    new_a = int(input())
    # print(new_a)
    if new_a <= global_min:
        colors.append([new_a, new_a])
        global_min = new_a
    else:
        for color in colors:
            if color[1] < new_a:
                color[1] = new_a
                break
    # print(colors)

print(len(colors))

Submission status: Wrong Answer

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

n = int(input())
a = [0]*n

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


if set(a) == n:
    print(n)
    exit()

ans = 0
pre = a[0]
for i in range(1, n):
    if pre >= a[i]:
        ans +=1
    pre = a[i]
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

r = [-1]
count = 0
for a in A:
    b = bisect.bisect(r, a)
    if r[b-1] != a and r[b-1] < a:
            r[b-1] = a
    else:
        r.insert(b, a)
print(len(r))

Submission status: Wrong Answer

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

Colors = deque()
Colors.append(A[0])

for i in range(1, N):
    if Colors[0] >= A[i]:
        Colors.appendleft(A[i])
    else:
        idx = bisect.bisect_right(Colors, A[i])
        Colors[idx-1] = A[i]
print(len(Colors))

Submission status: Wrong Answer

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

color = 1
maxv = A[N - 1]
maxvs = [maxv]
for k in range(N - 1):
    i = N - k - 2
    if A[i] < maxv:
        pass
    else:
        maxvs.append(A[i])
        maxv = max(maxvs)
        color += 1
print(color)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(input()) for i in range(n)]
color=0
sorta=sorted(a)
if sorta[0]==sorta[n-1]:
    print(n)
else:
    for i in range(n):
        if a[i]<=sorta[i]:
            color+=1
    print(color)

Submission status: Wrong Answer

Solution code:
len_arr = int(input())

arr = [int(input()) for _ in range(0, len_arr)]

current_min = {arr[-1]: 1}
num_color = 1

for i in reversed(range(0, len_arr-1)):
    target = arr[i]

    if target >= max(current_min.keys()):
        num_color += 1
        current_min[target] = 1
    else:
        acceptable = [x for x in current_min.keys() if x > target]
        selected = min(acceptable)

        if current_min[selected] == 1:
            del(current_min[selected])
            if target in current_min.keys():
                current_min[target] += 1
            else:
                current_min[target] = 1

        else:
            current_min[selected] -= 1

print(num_color)
exit(0)

Submission status: Wrong Answer

Solution code:
N = int(input())

colors = []
new_a = int(input())
colors.append([new_a, new_a])
global_min = new_a
for i in range(N-2):
    new_a = int(input())
    # print(new_a)
    if new_a <= global_min:
        colors.append([new_a, new_a])
        global_min = new_a
    else:
        for color in colors:
            if color[1] < new_a:
                color[1] = new_a
                break
    # print(colors)

print(len(colors))

Submission status: Wrong Answer

Solution code:
import bisect

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:
        midx = bisect.bisect_left(maxims,a)-1
        m = maxims[midx]
        if m == minim:
            minim = a
        maxims[midx] = a

    else:
        maxims=[a]+maxims
        ans += 1
        minim = a
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

cnt = 1

last = int(input())

buffer = [last]

for i in range(n - 1):
  a = int(input())
  # print(a, cnt)
  if a > last:
    last = a
  else:
    if len(buffer) == 0:
      buffer.append(last)
      cnt += 1
    if len(buffer) != 0:
      if a > buffer[-1]:
        last = a
        buffer.pop()
      else:
        buffer.append(last)
        cnt += 1
        last = a
    else:
      last = a
      cnt += 1
        
print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
B=[]
max=-1
max2=0
mini=100000000000
flag=0
point=10000000000
for i in range(N):
    x=int(input())
    B.append(x)

for i in range(N):
    #print(max)
    #x=int(input())
    #print(x)
    if B[i]>max:
        max=B[i]
    else:
        for i in range(len(A)):
            if max>A[i]:
                flag=1
                if mini>(max-A[i]):
                    mini=max-A[i]
                    point=i
        if flag==0:
            A.append(max)
            max=x
#print(B)
#print(A)
print(len(A)+1)

Submission status: Wrong Answer

Solution code:
import math



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)
        if S <= harf:
            search2(S)
        else:
            search(S)
        m = A[-1]
        harf = A[int(len(A)/2)]
    print(len(A))

    

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

Submission status: Wrong Answer

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

for j in range(1,n):
    if a[j]-a[j-1]<=0:
        b.append(b[j-1]+1)
    else: 
        b.append(b[j-1])    
c=[1]
for k in range(1,n):
    c.append(b[k]-b[k-1])

if c.count(0)==0:
    print(n)
else:
    print(n-(c.count(0)+1))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,math,heapq as hq
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())
aa = []
co = 0
ccc = 0
for i in range(1,n):
	if a[i] <= a[i-1]:
		if ccc != a[i-1]:
			aa.append([a[i-1],ccc])
			ccc = 0
		else:
			aa.append([a[i-1],0])
	else:
		if c == 0:
			ccc = a[i-1]
		c += 1
if ccc != a[-1]:
	aa.append([a[-1],ccc])
else:
	aa.append([a[-1],0])


d = cl.deque()
d.append(aa[0])
if aa[0][1] == 0:
	co += 1
for i in range(1,len(aa)):
	for j in range(len(d)):
		if d[-(j+1)][0] <= aa[i][0] and d[-(j+1)][0] > aa[i][1]:
			d.popleft()
			d.append(aa[i])
			break
	else:
		co += 1
		d.append(aa[i])
print(co)

Submission status: Wrong Answer

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

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

memo = []
saisho = 10000000000
for a in A:
    num = a[0]
    already = False
    if num < saisho:
        memo.append(num)
        saisho = num
    else:
        for i, m in enumerate(memo):
            if m < num:
                memo[i] = num
                break

print(len(memo))

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)

before = deque([])
cnt = 1
for i in range(N-1):
    if A[i] >= A[i+1]:
        before.append(A[i])
        cnt += 1
    
    if len(before) != 0:
        num = before[-1]
        if num < A[i+1]:
            before.pop()
            cnt -= 1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_right

def main():
    input = sys.stdin.readline
    N = int(input())
    q = list(map(int, input().split()))

    min_ = q[0]
    max_ = q[0]

    for _ in range(N-1):
        a = int(input())
        if a <= min_:
            q = [a] + q
            min_ = a
            continue
        if a > max_:
            q[-1] = a
            max_ = a
            continue

        pos = bisect_right(q, a)
        q = q[0:pos-1] + [a] + q[pos:]
        min_ = q[0]

    return len(q)


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
n = int(input())
colors = []
colors.append(int(input()))
for i in range(1, n):
  a = int(input())
  if a <= min(colors):
    colors.append(a)
  else:
    colors[colors.index(max(colors))] = a
print(len(colors))

Submission status: Wrong Answer

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

result_list = []

for a in a_list:
    max_num = 0
    connect_i = -1
    for i, l in enumerate(result_list):
        matsubi = l[-1]
        if a > matsubi:
            if max_num <= matsubi:
                max_num = matsubi
                connect_i = i
    if connect_i>=0:
#         print(i)
        result_list[i].append(a)
    else:
        result_list.append([a])

print(len(result_list))