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:
N=int(input())
A = []
for _  in range(N):
    A.append(int(input()))
ans = [A[0]]
min_ans = 1000000001
for n in range(1,N):
    if min_ans >= A[n]:
        ans.append(A[n])
        min_ans = A[n]
    else:
        for i in range(len(ans)):
            if ans[i] < A[n]:
                ans[i] = A[n]
                break
print(len(ans))

Submission status: Wrong Answer

Solution code:

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

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

Submission status: Wrong Answer

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

now = float('inf')
start = None
for a in A:
    if start is None:
        start = a
        now = a
        continue

    if now >= a:
        X.append(start)
        start = a
    now = a
else:
    if start is not None:
        X.append(start)


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(len(X))

X_sorted = {x: i for i, x in enumerate(sorted(X), start=1)}  # BITは1-indexd(0001からはじめたい)
ans = 0
for j, x in enumerate(X):
    ans += j - BIT.sum(X_sorted[x])
    BIT.add(X_sorted[x], 1)

print(len(X) - ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
# n = 6
# a = [5,6,7,2,6,4]

b = [a[0]]
minb = a[0]
count = 1
for i in range(1,n):
    if minb < a[i]:
        for j in range(len(b)):
            if b[j] < a[i]:
                b[j] = a[i]
    else:
        b += [a[i]]
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
r = int(input())
s = []
for i in range(r):
    s.append(int(input()))

co = 0
co = co +1
d = []
d.append(s[0])
for i in range(r) :
    #print(len(d))
    cc = 0
    if i == 0:
        continue
    for j in range(len(d)):
        if s[i] <= d[j]:
            cc = cc + 1
            if cc == len(d):
                d.append(s[i])
                break
            else:
                continue
        else:
            tmpd = 0
            b = 0
            for k in range(len(d)):
                if d[k] < s[i] and tmpd < d[k] :
                    tmpd = s[i]
                    b = k
            d[b] = tmpd
            break
print(len(d))

Submission status: Wrong Answer

Solution code:
import collections

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

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 = (diff <= 0).sum()
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

a = int(input())
maxVal = [a]

ans = 1
for _ in range(N-1) :
    a = int(input())
    i = 0
    for i in range(len(maxVal)) :
        if a <= maxVal[i] :
            maxVal.append(a)
            ans += 1
            break
    else :
        maxVal[i] = max(maxVal[i] , a)


print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())

lis = []

A1 = int(input())


lis.append(A1)


for i in range(N-1):

    A = int(input())

    flag = True

    for l in lis:

        if l < A:
            i = A
            flag = False
            lis.sort()
            break

    if flag:
        lis.append(A)

#print (lis)
print (len(lis))

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 bi == dp[-1]:
        dp += num,
    else:
        dp[bi] = num
print(len(dp))

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
a_list = [(i, int(input())) for i in range(n)]
a_list.sort(key=lambda a: a[1])

min_i = n
count = 0
for a, group in itertools.groupby(a_list, lambda a: a[1]):
    for i, _ in sorted(group, key=lambda a: -a[0]):
        if i < min_i:
            count += 1
            min_i = i
print(count)

Submission status: Wrong Answer

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

B = [A[0]]

for i in range(1,N):
    if A[i]<=B[-1]:
        B.append(A[i])
    elif A[i]>B[0]: 
        B[0] = A[i]
    else:
        l = 0
        r = len(B)-1
        while l+1<r:
            c = (l+r)//2
            if B[c]>=A[i]:
                l = c
            elif B[c]<A[i]:
                r = c
        if A[l]<A[i]:      
            A[l] = A[i]
        else:      
            A[r] = A[i]
print(len(B))

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:
  A0 = min(A)
  A.pop(A.index(A0))
  cnt += 1
  i = 0
  while i < len(A):
    if A[i] > A0:
      A.pop(i)
    else:
      i += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
A = []
ans = 1
idx = -1
A = [int(input()) for _ in range(N)]
for i in range(1, N):
    if A[i-1] >= A[i]:
        if idx == -1:
            idx = i-1
            ans += 1
        else:
            if A[idx] >= A[i]:
                ans += 1
                idx = i
            else:
                idx = i
print(ans)

Submission status: Wrong Answer

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

check = [False for _ in range(N)]
cnt = 0
while len(A) > 0:
  A0 = min(A)
  A.pop(A.index(A0))
  cnt += 1
  i = 0
  while i < len(A):
    if A[i] > A0:
      A.pop(i)
    else:
      i += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = [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.append(a)
        surfMin = a
    elif a>surfMax:
        surface[color-1] = a
        surfMax = a
    else:
        pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
        surface[pos] = a
print(color)

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]:
    k-=1
    if k<0:k=d;d+=1
  elif a[i]==a[i-1]:d+=1
print(d)

Submission status: Wrong Answer

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


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

print(len(ls))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
count = 0
def cal(a):
  first = a[0]
  return [i for i in a if i<=first][1:]
while len(a) != 0:
  a = cal(a)
  count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq

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

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

print(len(alist))

Submission status: Wrong Answer

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

ans = 1
a_last = A[0]

for i in range(1, n):
    a = A[i]
    if a <= a_last:
        ans += 1
    a_last = min(a_last, a)


print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = []
for _ in range(N):
    a = int(input())
    A.append(a)
    
BALL = A[:]
ans = 0
max_num = 0
for b in BALL:
    if b > max_num:
        max_num = b
    else:
        ans += 1

    
print(ans)

Submission status: Wrong Answer

Solution code:

import bisect as bs
import collections

n = int(input())
alist = [0]*n
for i in range(n):
    alist[i] = int(input())

col = collections.deque()
min_ = 1000000000

for a in alist:
    if a <= min_:
        col.appendleft(a)
    else:
        index = bs.bisect(col, a) - 1
        ind = bs.bisect_left(col, col[index])
        col[ind] = a
    min_ = min(col)

print(len(col))

Submission status: Wrong Answer

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

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

old=-1
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)

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

for i in range(n):
	a.append(onem())
aa = []
for i in range(1,n):
	if a[i] <= a[i-1]:
		aa.append(a[i-1])
aa.append(a[-1])

co = 1

C = [aa[0]]

for i in range(1,len(aa)):
	if C[0] < aa[i]:
		hq.heappop(C)
		hq.heappush(C,aa[i])
	else:
		co += 1
		hq.heappush(C,aa[i])
print(co)

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]:
    k-=1
    if k<0:k=d;d+=1
print(d)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
A = []
ans = 1
idx = -1
A = [int(input()) for _ in range(N)]
for i in range(1, N):
    if A[i-1] >= A[i]:
        if idx == -1:
            idx = i
            ans += 1
        else:
            if A[idx] >= A[i]:
                ans += 1
                idx = i
            else:
                idx = i
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N=int(input())

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

print(len(lasts))

Submission status: Wrong Answer

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

check = [False for _ in range(N)]
cnt = 0
while len(A) > 0:
  A0 = A[0]
  cnt += 1
  i = 1
  while i < len(A):
    if A[i] > A0:
      A.pop(i)
    else:
      i += 1
  A.pop(0)
print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
mi = 10**9
count = 0
for i in range(N):
    k = int(input())
    if k <= mi:
        count += 1
        mi = k
print(count)

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  # 二分探索

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:
            B.append(a)
    print(len(B))

main()

Submission status: Wrong Answer

Solution code:
N = int(input())

A = []
for _ in range(N):
    a = int(input())
    A.append(a)
    
BALL = A[:]
ans = 0
min_num = 10 ** 9 + 7
for b in BALL:
    if b > min_num:
        continue
    else:
        min_num = b
        ans += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
input = raw_input

# import random
# print(100000)
# x = [random.randint(1,1000000000) for i in range(100000)]
# for i in x:
#     print(i)
# exit()

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

C = [0] * N
c = 0
for i in range(N):
    if C[i] == 0:
        c += 1
        C[i] = c
        m = C[i]
        for j in range(i+1,N):
            if C[j] == 0:
                if A[j] > m:
                    C[j] = c
                    m = A[j]
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
counter = 1
A = []
for _ in range(n):
  i = int(input())
  A.append(i)
for t in range(n-1):
  if A[t+1] == A[t]:
    counter += 1
  if A[t+1] < A[t] and counter == 1:
    counter +=1
    
print(counter)

Submission status: Wrong Answer

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

res = 1
m = a[0]
for i in a[1:]:
    if i <= m:
        m = i
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
m = (10**9)+1
c = 0
f = 0
b = (10**9)+1
for i in range(n):
	tmp = int(input())
	if m >= tmp:
		if b >= tmp:
			c+=1
			m = tmp
			b = tmp	
		else:
			b = m
			m = tmp
	else:
		m = tmp
print(c)

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
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

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

def main():
    n=INT()
    a = [INT() for _ in range(n)]
    color = 0
    for i in range(n-1):
        if a[i+1] < a[i]:
            color += 1

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
array = []
for i in range(n):
    array.append(int(input()))
color = 1
lis = array[0]
for i in range(n-1):
    if array[i] < array[i + 1]:
        continue
    else:
        if lis < array[i]:
            lis = array[i]
        else:
            color += 1
print(color)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

num_col = 1
L = [-1*Alist[0]] ###各色の末尾の数字
for ai in Alist[1:]:
    ai = -1*ai
    if ai >= L[-1]:
        L.append(ai)
        num_col += 1
    else:
        L[bisect_left(L, ai)] = ai
print(num_col)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(input()) for i in range(n)]
ans = 0
while len(A) != 0:
    tmp = [A[i] for i in range(1,len(A)) if A[i]<=A[i-1]]
    A = tmp
    tmp =[]
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""


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

def main():
    nmin = 10**9
    cnt = 0
    for n in range(N):
        if A[n] < nmin:
            nmin = A[n]
            cnt += 1
        elif A[n] == nmin:
            cnt+=1
        else:
            pass
    print(cnt)
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
f = [0]*(n+1)
s = set()
count = 0
for i in range(n):
  ai = int(input())
  a.append(ai)
  s.add(ai)
  
if(len(s)==1):
  ans = n
else:
  ans = 0
  while(count<n):
    for i in range(n):
      if(f[i]==0):
        f[i] = 1
        flag = 0
        ans = ans + 1
        count += 1

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ans = 1
a_last = A[0]

for i in range(1, n):
    a = A[i]
    if a <= a_last:
        ans += 1
        a_last = min(a_last, a)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
a = np.array([int(input()) for i in range(n)])
if len(set(a)) ==1:
  print(n)
else:
  diff = np.diff(a)
  ans = (diff <= 0).sum()
  print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

num_col = 1
L = [-1*Alist[0]] ###各色の末尾の数字
for ai in Alist[1:]:
    ai = -1*ai
    if ai > L[-1]:
        L.append(ai)
        num_col += 1
    else:
        L[bisect_left(L, ai)] = ai
print(num_col)

Submission status: Wrong Answer

Solution code:
from heapq import *
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, m, flag = 1, [-A[0]], A[0], 1
    for a in A[1:]:
        if a <= m:
            m = a
            heappush(ms, -a)
            cnt += 1
            if cnt > mid:
                flag = 0
                break
        else:
            heapreplace(ms, -a)
            m = min(m, a)
    if flag:
        ub = mid
    else:
        lb = mid
cnt, ms, m, flag = 1, [-A[0]], A[0], 1
for a in A[1:]:
    if a <= m:
        m = a
        heappush(ms, -a)
        cnt += 1
        if cnt > mid:
            flag = 0
            break
    else:
        heapreplace(ms, -a)
        m = min(m, a)
if flag:
    print(mid)
else:
    print(mid+1)

Submission status: Wrong Answer

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

n = 1
cur = 1
for i in range(1, N):
  if A[i-1] >= A[i]:
    cur += 1
    if n < cur:
      n = cur
  else:
    cur = 1
print(n)

Submission status: Wrong Answer

Solution code:
import copy

N = int(input())
A = []
for i in range(N):
	A.append(int(input()))
	
mnmm = max(A) + 1
ctr = 0
for i in range(N):
	if A[i] <= mnmm:
		ctr += 1
		mnmm = A[i]

print(ctr)

Submission status: Wrong Answer

Solution code:
from heapq import *
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, m, flag = 1, [-A[0]], A[0], 1
    for a in A[1:]:
        if a <= m:
            m = a
            heappush(ms, -a)
            cnt += 1
            if cnt > mid:
                flag = 0
                break
        else:
            heapreplace(ms, -a)
            m = min(m, a)
    if flag:
        ub = mid
    else:
        lb = mid
cnt, ms, m, flag = 1, [-A[0]], A[0], 1
for a in A[1:]:
    if a <= m:
        m = a
        cnt += 1
        if cnt > mid:
            flag = 0
            break
    else:
        heapreplace(ms, -a)
        m = min(m, a)
if flag:
    print(mid)
else:
    print(mid+1)

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
L = []
L.append(int(input()))
c = 1

for i in range(N - 1):
	A = -int(input())
	x = bisect.bisect_right(L, A)
	if x == c:
		L.append(A)
		c += 1
	else:
		L[x] = A

print(c)

Submission status: Wrong Answer

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

b = a[0]
count = 1
for i in range(1,n):
    if b >= a[i]:
        b = a[i]
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
As = []
for i in range(N):
  A = int(input())
  As.append(A)
num = 1
s = []
c = As[0]
for i in range(1,N):
  A = As[i]
  if c < A:
    #print(i, A, "A")
    c = A
  else:
    index = -1
    for j in reversed(range(len(s))):
      if s[j] < A:
        index = j
        break
    #print(s, A)
    #print(index)
    if index >= 0:
      #print(i, A, "B", index)
      s = s[0:index]
      c = A
    else:
      #print(i, A, "C")
      num += 1
      s.append(c)
      c = A
print(num)

Submission status: Wrong Answer

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


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def inversion(a):
    "転倒数を求める"
    d = {av: i+1 for i, av in enumerate(sorted(a))}
    b = Bit(len(a))
    ans = 0
    for i, av in enumerate(a):
        b.add(d[av], 1)
        ans += i+1-b.sum(d[av])
    return ans


def solve(N: int, A: "List[int]"):
    print(N-inversion(A))
    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())
a = [int(input()) for _ in range(n)]

import bisect
min_list = [-1]
for i in reversed(range(n)):
    if a[i] >= min_list[-1]:
        min_list.append(a[i])
    else:
        insert_index = bisect.bisect_left(min_list, a[i])
        min_list[insert_index] = a[i]


print(len(min_list) - 1)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import deque

readline = stdin.readline


def nf():
    """
    入力全て(EOFまで)を`int iter`に変換
    """
    return map(int, open(0).read().split())


def main():
    _, *al = nf()
    res = 1
    q = deque(())
    for a, b in zip(al[:-1], al[1:]):
        if a >= b:
            try:
                f = q[0]
                if f < b:
                    q.popleft()
                    continue
            except IndexError:
                pass
            q.append(a)
            res += 1
    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC134e
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
a = []
b = 10**9

for _ in range(n):
    a.append(int(input()))

c = 0
for i in range(n):
    if (a[i] <= b):
        c += 1
        b = a[i]
print(c)

Submission status: Wrong Answer

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

from bisect import bisect_left


def lis(a):
    length = [a[0]]
    for i in range(1, len(a)):
        if a[i] >= length[-1]:
            length.append(a[i])
        else:
            length[bisect_left(length, a[i])] = a[i]
    return len(length)


print(lis(a))

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


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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

ans = 0
for i in range(len(lis)):
    l,r,f = lis[i]
    if f:
        continue
    for j in range(i+1, len(lis)):
        if not lis[j][2] and lis[j][0] > r:
            r = lis[j][1]
            lis[j][2] = 1
    ans += 1
print(ans)