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

ans = 0
if sum(a) == 0:
    print(n)
else:
    for i in range(n):
        if sum(a) == 0:
            break
        else:
            for j in range(1, len(a)):
                b = a[0]
                a[0] = 0
                if a[j] > b:
                    b = a[j]
                    a[j] = 0
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
N = int(input())						# 5

A=[]

a = int(input())
A.append(a)

for i in range(1,N):
	a = int(input())
	A.append(a)


B=[A[0]]

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

#	p("  i, B",i,B)
#
#
#p("A",A)
#p("B",B)

print( len(B) )

Submission status: Wrong Answer

Solution code:
n = int(input())
t = int(input())

ans = 1

for i in range(n-1):
    s = int(input())
    if t >= s:
        ans += 1
        t = s

print(ans)

Submission status: Wrong Answer

Solution code:
import sys,re,copy
input = sys.stdin.readline

N=int(input().strip())

ans=[0 for _ in range(N)]
ans[0]=int(input().strip())

for _ in range(N-1):
    A=int(input().strip())
    for i,m in enumerate(ans):
        if A>m:
            ans[i]=A
            break

print(len([x for x in ans if x != 0]))

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.insert(0,a)
        ans += 1
        minim = a
print(ans)

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]
for k in range(N - 1):
    i = N - k - 2
    if A[i] < maxv:
        pass
    else:
        maxv = A[i]
        color += 1
print(color)

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)
    # 前の値よりも小さい値の時
    else:
        # かつ色数が 2色未満ならば
        if maxCol == 1:
            col += 1
            maxCol = 2
        else:
            col = 1
    beforeV = A[i]

print(maxCol)

Submission status: Wrong Answer

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

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

min_ = 10 ** 10
count = 0

for a in range(len(A)-1):
    if A[a] <= min_:
        min_ = A[a]
        count+= 1

if A[a] == min_:
    count += 1
        
print(count)

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
        continue
    
    if len(before) != 0:
        num = before[-1]
        if num < A[i+1]:
            before.pop()
            cnt -= 1
    
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
t = int(input())

ans = 1

for i in range(n-1):
    s = int(input())
    if t >= s:
        ans += 1

print(ans)

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
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 = []
sln = []


def update_solution(sln, k):
    ln = len(sln)
    if ln == 0 or k <= sln[0]:
        return [k] + sln
    l = 0
    r = ln - 1
    while r > l + 1:
        m = (l + r) // 2
        if sln[m] < k:
            l = m
        else:
            r = m
    sln[r] = k
    return sln


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

print(len(sln))

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

fin = sys.stdin.readline
N = [int(elem) for elem in fin().split()][0]
a_list = [[int(elem) for elem in fin().split()][0] for _ in range(N)]


list_count = 0
num_list = [[list_count, a_list[0]]]
prev_a = a_list[0]
for each_a in a_list[1:]:
    if prev_a >= each_a:
        num_list[-1].append(prev_a)
        list_count += 1
        num_list.append([list_count, each_a])
    prev_a = each_a
num_list[-1].append(a_list[-1])


# print(sorted(num_list, key=itemgetter(2)))
num_list = sorted(num_list, key=itemgetter(2))
count = 1
prev_start = num_list[0][1]
prev_last = num_list[0][2]
for each_list in num_list[1:]:
    current_start = each_list[1]
    current_last = each_list[2]
    if prev_last >= current_start:
        count += 1
    prev_start = current_start
    prev_last = current_last

print(count)

Submission status: Wrong Answer

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

Solution code:
N = int(input())
# A_list = [0 for i in range(N)]
colors = []
num_of_colors = 0
for i in range(N):
    max_num = 0
    target = -1
    ai = int(input())
    for j in range(num_of_colors):
        if ai > colors[j]:
            if max_num < colors[j]:
                max_num = colors[j]
                target = j
            # colors[j] = ai
            # num_of_colors += 1
            # break
    if target == -1:
        colors.append(ai)
        num_of_colors += 1
    colors[target] = ai
    # A_list[i] = ai

# print(A_list)
# print(colors)
print(num_of_colors)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = [int(input()) for _ in range(n)]
print(a)
ans=0
while sum(a)!=-n:
  b=a[ans]
  a[ans]=-1
  ans+=1
  a = [-1 if i > b else i for i in a]
print(ans)

Submission status: Wrong Answer

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

import heapq


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    heapq.heappush(heads, -a)
    while A:
        a = A.pop()
        h = -heapq.heappop(heads)
        if a < h:
            heapq.heappush(heads, -a)
        else:
            heapq.heappush(heads, -a)
            heapq.heappush(heads, -h)
    return len(heads)
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
A_sort = sorted(A, reverse=True)

cnt = 0
for a in A:
    while len(A_sort):
        if a not in set(A_sort):
            break
        else:
            del A_sort[:A_sort.index(a) + 1]
            cnt += 1
            break
print(cnt)

Submission status: Wrong Answer

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
num_line = [stdin.readline().rstrip() for _ in range(N)]
for i in range(N):
    save_num = num_line[i]
    num_line.pop(i)
    print(max(num_line))
    num_line.insert(i, save_num)

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)):
	if d[0][0] <= aa[i][0] and d[0][0] > aa[i][1]:
		d.popleft()
		d.append(aa[i])
	else:
		co += 1
		d.append(aa[i])
print(co)

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
c = readi()
count = 1
for i in range(n - 1):
    k = readi()
    if k > c:
        pass
    else:
        c = min(c, k)
        count += 1
print(count)

Submission status: Wrong Answer

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

import bisect
X=[A[0]]
for i in range(1,N):
    n = len(X)
    a = A[i]
    at = bisect.bisect_right(X,a)
    if at >= n:
        if X[at-1] != a:
            X[at-1] = a
        else:
            X.append(a)
    elif at == 0:
        X.insert(0,a)
    else:
        if X[at-1] != a:
            X[at-1] = a
        else:
            X.insert(at,a)

print(len(X))

Submission status: Wrong Answer

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

def merge(a, b):
    global ret
    arr = []
    ai = 0
    bi = 0
    while ai < len(a) or bi < len(b):
        if bi == len(b):
            arr.append(a[ai])
            ai += 1
        elif ai == len(a):
            arr.append(b[bi])
            bi += 1
        elif ai < len(a) and a[ai] >= b[bi]:
            arr.append(b[bi])
            bi += 1
            ret += 1
        else:
            arr.append(a[ai])
            ai += 1
    return arr

while len(a) > 1:
    newa = []
    for i in range(len(a) // 2):
        newa.append(merge(a[i * 2], a[i * 2 + 1]))
    if len(a) % 2 == 1:
        newa.append(a[len(a) - 1])
    a = newa

print(ret)

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
        continue
    
    if len(before) != 0:
        num = before.pop()
        if num < A[i+1]:
            cnt -= 1
    
print(cnt)

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]:
        return [k] + sln
    l = 0
    r = ln - 1
    while r > l + 1:
        m = (l + r) // 2
        if sln[m] < k:
            l = m
        else:
            r = m
    sln[r] = k
    return sln


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

print(len(sln))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
seq = []
colors = []
largest = []

def bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid][0] < x: 
            lo = mid+1
        else: hi = mid
    return lo

for i in range(n):
    num = int(input())
    seq.append(num)
    if i == 0:
        colors.append([num])
        largest.append([num,0])
    else:
        pos = bisect_left(largest, num)
        if pos == 0:
            bisect.insort(largest, [num, len(colors)])
            colors.append([num])
        else:
            if pos >= len(largest):
                pos -= 1
                largest[pos][0] = num
                pos = largest[pos][1]
                colors[pos].append(num)
        largest.sort()
            

        
print(len(colors))

Submission status: Wrong Answer

Solution code:
import bisect

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for _ in [0]*N]
B = [A[0]]
ans = 1

for a in A[1:]:
    l = 0
    r = ans - 1
    if B[0]<a:r=0
    while l+1<r:
        i = (l+r)//2
        if B[i] >= a:
            r = i
        else:
            l = i
    if B[r]<a:B[r] = a
    else:
        B.append(a)
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
mi = 10000000000000
res = 0

for i in range(n):
    if dat[i] <= mi:
        res += 1
        mi = dat[i]
print(res)

Submission status: Wrong Answer

Solution code:
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
N = int(input())						# 5

A=[]

a = int(input())
A.append(a)

for i in range(1,N):
	a = int(input())
	A.append(a)


B=[-1]

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

#	p("  i, B",i,B)
#
#
#p("A",A)
#p("B",B)

print( len(B) )

Submission status: Wrong Answer

Solution code:
N = int(input())
As = []
for i in range(N):
    As.append(int(input()))
Fs = [False for _ in range(N)]

c = 0
for i in range(N):
    if Fs[i] == False:
        c += 1
        Fs[i] = True
        for j in range(i + 1, N):
            if (As[j] > As[i]):
                Fs[j] = True
print(c)

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:
        cnt += 1
        last = a
        
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = 1000000000
ans = 1
for i in range(n):
  m = int(input())
  a.append(m)
  if i == 0:
    continue
  elif a[i-1] < a[i]:
    continue
  elif a[i] > b:
    continue
  else:
    b = a[i]
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)
B = []
B.append(A[0])
pre = A[0]
cnt = 0
for i in range(1, N):
    if A[i] > B[cnt] and A[i] > pre:
        pass
    elif A[i] <= pre:
        if A[i] <= B[cnt]:
            pre = A[i]
            B.append(A[i])
            cnt += 1
        elif A[i] > max(B):
            pre = A[i]     
print(cnt+1)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = [INT() for _ in range(N)]

# tmp = 0
# ans = 0
# for i in range(1, N):
# 	print(A[i-1], A[i])
# 	if A[i] < A[i-1]:
# 		ans += 1
# print(ans)
seq = A

ans = 0
LIS = [seq[0]]
for i in range(len(seq)):
	if seq[i] > LIS[-1]:
		LIS.append(seq[i])
	else:
		if bisect.bisect_left(LIS, seq[i]) == 0:
			ans += 1
		LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]

print(ans)

Submission status: Wrong Answer

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


main()

Submission status: Wrong Answer

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n = readi()
c = readi()
count = 1
for i in range(n - 1):
    k = readi()
    if k > c:
        pass
    else:
        c = max(c, k)
        count += 1
print(count)

Submission status: Wrong Answer

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

for i in range(1, n):
  min_nums = min(nums)
  nn = int(input())
  
  # すでにあるリストのどの数よりも小さければ、リストに追加する
  if nn <= min_nums:
    nums.append(nn)
  
  # リストのある数よりも大きければ、その要素を上書きする
  else:
    # nnより小さく、差が最小のインデックスを選ぶ
    nums_d = min([num for num in nums if num < nn])
    min_nums_d_index = nums.index(nums_d)
    
    # 置き換える
    nums[min_nums_d_index] == nn
    
print(len(nums))

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N = INT()
    A = [INT() for i in range(N)]
    maxv = []
    for i in range(N - 1):
        if A[i] >= A[i + 1]:
            maxv.append(A[i])
    maxv.append(A[-1])
    maxv.reverse()
    sumv = 0
    for i in range(len(maxv)-1):
        if maxv[i] <= maxv[i + 1]:
            sumv += 1
    print(sumv + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

max_color = 1
cnt_color = 1
stack = []
p = -1

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

print(max_color)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    counter = 0
    m = 1e12
    for i in range(N):
        if A[i] <= m:
            counter +=1
            m = A[i]
    print(counter)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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())

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
      else:
        cnt += 1
        last = a
        
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
  a.append(int(input()) * 10 ** 5 - i)
b = sorted(a)
print(a)
print(b)
count = 0
import random
while True:
  now = a[count]
  count += 1
  head = 0
  back = len(b)-1
  j = 0
  while b[j] != now:
    if b[j] > now:
      back = j
    else:
      head = j
    j = random.randrange(head,back+1)
  b = b[:j]
  if b == []:
    break
print(count)

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_left(seen, a)
    seen.append(a)
    if lower < bigger:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:

def binSearch(S, x):
    a = -1
    b = len(S)-1

    while(a + 1 < b):
        c = (a+b)//2
        if S[c] > x:
            a = c
        else:
            b = c

    return b

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

    S = []

    for a in A:
        if len(S) == 0 or S[-1] >= a:
            S.append(a)
        else:
            p = binSearch(S, a)
            S[p] = a
    
    print(len(S))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import *
from bisect import bisect_right, bisect_right
from collections import deque
N = int(input())
A = [int(input()) for i in range(N)]
lb, ub = 0, N
while lb + 1 < ub:
    mid = (lb+ub)//2
    cnt, ms, flag = 1, deque(), 1
    ms.append(A[0])
    for a in A[1:]:
        if a <= ms[0]:
            ms.appendleft(a)
            cnt += 1
            if cnt > mid:
                flag = 0
                break
        else:
            i = bisect_right(ms, a)-1
            ms[i] = a
    if flag:
        ub = mid
    else:
        lb = mid
cnt, ms, flag = 1, deque(), 1
ms.append(A[0])
for a in A[1:]:
    if a <= ms[0]:
        ms.appendleft(a)
        cnt += 1
        if cnt > mid:
            flag = 0
            break
    else:
        i = bisect_right(ms, a)-1
        ms[i] = a
if flag:
    print(mid)
else:
    print(mid+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]+[int(input()) for _ in range(N)]
ans = 0

for i in range(1,N):
    if a[i-1] < a[i]:
        ans += 1

print(N-ans)

Submission status: Wrong Answer

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

from bisect import bisect_left
	
def LIS(L) :   
    lis = [L[0]]
    for a in L[1:] :
        if a >= lis[-1] :
            lis.append(a)
        else :
            s = bisect_left(lis, a)
            lis[s] = a
    return len(lis)

print(LIS(A[::-1]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
count=0
for i in range(n):
    a.append(int(input()))
for k in range(n):
    if a[k]!=-1:
        temp=a[k]
        a[k]=-1
        count+=1
        for i in range(n):
            if temp<a[i]:
                temp=a[i]
                a[i]=-1
print(0)

Submission status: Wrong Answer

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

import heapq


def solve():
    N = int(input())
    A = []
    tails = []
    for _ in range(N):
        A.append(int(input()))
    A.reverse()
    a = A.pop()
    heapq.heappush(tails, a)
    while A:
        a = A.pop()
        t = heapq.heappop(tails)
        if a > t:
            heapq.heappush(tails, t)
        else:
            heapq.heappush(tails, a)
            heapq.heappush(tails, t)
    return len(tails)
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
numofcolor = 1
A = [0] * N
for i in range(N):
    A[i] = int(input())
listofmax = [A[0]]
lenoflistofmax = 1  # 実際のところnumofcolorと同じ値になる
for j in range(1, N):
    if listofmax[0] > A[j]:
        numofcolor += 1
        lenoflistofmax += 1
        listofmax.insert(0, A[j])
    else:
        listofmax[bisect.bisect_left(listofmax, A[j]) - 1] = A[j]
print(numofcolor)

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:
        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)]

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:]:
    print(m,M)
    if a <= m:
        ans += 1
        m = a
    elif m < a <= M:
        m = a
    elif M < a:
        M = a

print(ans)

Submission status: Wrong Answer

Solution code:
words = lambda t : list(map(t, input().split()))
n = int(input())
a = []
for i in range(n):
    x = int(input())
    a.append((x,i))

a.sort()

ans = 1
min_i = a[0][1]

for i in range(1,n):
    if a[i][0] == a[i-1][0]:
        ans+= 1
    elif a[i][1] < min_i:
        ans+= 1
    min_i = min(min_i, a[i][1])

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 == 1):
    two = 0
stdout.write(str(two + 1))

Submission status: Wrong Answer

Solution code:
N  =int(input())
A = list(int(input()) for _ in range(N))
B = []
cnt = 0
while len(A) >= 2:
    ai = A[0]
    aj = A[1]
    B.append(A.pop(0))
    i = -1
    j = i+1
    while j < len(A):
        if ai < aj:
            ai = aj
            i = j-1
            B.append(A.pop(j))
            j = i+1
            if j < len(A)-1:
                aj = A[j]
        elif j == len(A)-1:
            j += 1
        else:
            j += 1
            aj = A[j]
    cnt += 1
if A:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
a=int(input())
b=[int(input()) for i in range(a)]
c=0
while b!=[]:
  c+=1
  d=b[0]
  b.pop(0)
  i=0
  f=len(b)
  while i<f:
    if d<b[i]:
      d=b[i]
      b.pop()
      f-=1
    else:
      i+=1
print(c)

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
elif (two == 1):
    two = 0
stdout.write(str(two + 1))