Problem:


Score : 500 points

Problem Statement

You are given a sequence with N integers: A = \{ A_1, A_2, \cdots, A_N \}.
For each of these N integers, we will choose a color and paint the integer with that color. Here the following condition must be satisfied:

If A_i and A_j (i < j) are painted with the same color, A_i < A_j.

Find the minimum number of colors required to satisfy the condition.

Constraints

1 \leq N \leq 10^5

0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the minimum number of colors required to satisfy the condition.

Sample Input 1

5
2
1
4
5
3

Sample Output 1

2

We can satisfy the condition with two colors by, for example, painting 2 and 3 red and painting 1, 4, and 5 blue.

Sample Input 2

4
0
0
0
0

Sample Output 2

4

We have to paint all the integers with distinct colors.



Sample input:
5
2
1
4
5
3


Sample output:
2

Submission status: Wrong Answer

Solution code:
"""
A = a1,a2,a3,a4,...
同じ色のとき、i<jならai<aj

が成り立つときの最小の色の数

2 1 4 5 3

8
5 
4 
3 
2 
1 
3 
2 
1

5
4
3
2 3
1 2
1



"""

from bisect import bisect_right

prev = 10**9+7
cnt = 0
As = [-prev]
n = int(input())
for _ in range(n):
    a = int(input())
    if prev >= a:
        update = bisect_right(As,-a)
        if update-1 == cnt:
            As.append(-a)
            cnt += 1
        else:
            As[update-1] = -a 
    prev = a

print(cnt)

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

from bisect import bisect_right as br
from bisect import bisect_left  as bl
from bisect import insort_right as ir
from bisect import insort_left  as il


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

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

	r = br(B,a)
	if a>B[-1]:
		B[-1]=a
	elif a<B[0]:
		B = [a]+B
	else:
		B[r-1]=a


	p("  i,a,r,B ",i,a,r,B)


p("B",B)

print( len(B) )

Submission status: Wrong Answer

Solution code:
n = int(input())
an = [0]*n
for i in range(0, n):
    an[i] = int(input())
dp = [-1] * n

len = 1
dp[0] = an[0]
for i in range(1,n):
    if dp[len-1] >= an[i]:
        dp[len] = an[i]
        len += 1
        continue
    
    idx = len // 2
    r = len-1
    l = 0
    while(True):
        if dp[idx] == an[i]:
            break
        elif dp[idx] > an[i]:
            if r == idx+1:
                dp[r-1] = an[i]
                break
            else:
                l = idx
                idx = idx + (r - idx) // 2
        else:
            if l == idx:
                dp[l] = an[i]
                break
            else:
                r = idx
                idx = l + (idx - l) // 2
    
print(len)

Submission status: Wrong Answer

Solution code:
import copy

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = 1
ans = 1
tmp = int(input())
for i in range(1,N):
    A = int(input())
    if A <= tmp:
        memo += 1
    else:
        memo = 1
    tmp = A
    ans = max(ans,memo)
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_ = 10000000000

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

print(len(col))

Submission status: Wrong Answer

Solution code:
import copy

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = 1
ans = []
tmp = int(input())
for i in range(1,N):
    A = int(input())
    if A <= tmp:
        memo += 1
    else:
        ans.append(memo)
        memo = 1
    tmp = A
ans.append(memo)
print(max(ans))

Submission status: Wrong Answer

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

cnt = 0
maxcnt = 0

for i in range(1, N) :

    if A[i-1] >= A[i] :
        cnt += 1
    else :
        if cnt > maxcnt :
            maxcnt = cnt
        cnt = 0

print(cnt+1)

Submission status: Wrong Answer

Solution code:
import copy

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

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

Submission status: Wrong Answer

Solution code:
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_ = 10000000000

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

print(len(col))

Submission status: Wrong Answer

Solution code:
n = int(input())
seq = [0]*n
for i in range(n):
  seq[i] = int(input())
  
count = 0

for i in range(n-1):
  if seq[i]-seq[i+1]>= 0:
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import io
import sys


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
5
5
4
3
5
2
1
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()

  l = []
  
  snum = -1
  pnum = -1
  for i in range(0, n):
    num = IN_I()
    # print("num:", num )
    if pnum < num:
      pnum = num
      continue

    # print(l, num)
    for j in range(0, len(l) + 1):
      # print(j, len(l))
      if j == len(l):
        # print("l append", pnum)
        l.append(pnum)
      else:
        if l[j] < snum:
          l[j] = pnum
          print (l[j], pnum)
          break

    # print ("pnum", num)
    snum = pnum = num

  if pnum > -1:
    for j in range(0, len(l) + 1):
      if j == len(l):
        l.append(pnum)
      else:
        if l[j] < snum:
          l[j] = pnum
          break

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Wrong Answer

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

def bisect(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] > x: 
            lo = mid+1
        else: 
            hi = mid
    return lo

for i in range(n):
    num = int(input())
    if i == 0:
        colors.append(num)
    else:
        pos = bisect(colors, num)
        if pos > len(colors) - 1:
            colors.append(num)
        elif colors[pos] == num and colors[-1] == num:
            colors.append(num)
        else:
            colors[pos] = num
            
print(len(colors))

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

def LIS(L):
  L = L[::-1]
  LIS=[L[0]]
  L.pop(0)
  for i in L:
    if i >= LIS[-1]:
      LIS.append(i)
    else:
      LIS[bs.bisect_left(LIS,i)]=i
  return len(LIS)

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())


print(LIS(a))

Submission status: Wrong Answer

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

cnt = 0
maxcnt = 0

for i in range(N) :
    if i == 0 :
        if A[i] >= A[i+1] :
            cnt += 1
        continue
    if A[i-1] >= A[i] :
        cnt += 1
    else :
        if cnt > maxcnt :
            maxcnt = cnt
        cnt = 0

print(cnt+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect as bl

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

def lds(X: list):
    L = [-X[0]]
    for x in X[1:]:
        if L[-1] <= -x:
            L.append(-x)
        else:
            L[bl(L, -x)] = -x
    return L

print(lds(A))

Submission status: Wrong Answer

Solution code:
import bisect

n=int(input())
arr=[int(input()) for _ in range(n)][::-1]
LIS = [arr[0]]
for i in range(1,n):
  if arr[i] >= LIS[-1]:
    LIS.append(arr[i])
  else:
    LIS[bisect.bisect_left(LIS, arr[i])] = arr[i]
print(len(LIS))

Submission status: Wrong Answer

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

def bisect(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] > x: 
            lo = mid+1
        else: 
            hi = mid
    return lo

for i in range(n):
    num = int(input())
    if i == 0:
        colors.append(num)
    else:
        pos = bisect(colors, num)
        if pos > len(colors) - 1:
            colors.append(num)
        elif colors[pos] == num:
            colors = colors[:pos + 1] + [num] + colors[pos+1:]
        else:
            colors[pos] = num
            
print(len(colors))

Submission status: Wrong Answer

Solution code:
import bisect
def LIS():
    L[0] = A[0]
    length = 1
    for i in range(1, N):
        if L[length-1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

def LISDesc():
    L[0] = A[-1]
    length = 1
    for i in range(N-2, -1, -1):
        if L[length-1] <= A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

INFTY = 10**13
N = int(input())
A = [int(input()) for i in range(N)]
L = [INFTY for i in range(N)]
ans = LISDesc()
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))

def LIS(L):
  L = L[::-1]
  LIS=[L[0]]
  L.pop(0)
  for i in L:
    if i >= LIS[-1]:
      LIS.append(i)
    else:
      LIS[bs.bisect_left(LIS,i)]=i
  return len(LIS)

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())
aa = []
co = 0

print(LIS(a))

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_ = alist[0]

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

print(len(col))

Submission status: Wrong Answer

Solution code:
import bisect
def LIS():
    L[0] = A[0]
    length = 1
    for i in range(1, N):
        print(A[i])
        if L[length-1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

def LISDesc():
    L[0] = A[-1]
    length = 1
    for i in range(N-2, -1, -1):
        if L[length-1] <= A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_left(L, A[i])
            print(i, A[i], j)
            L[min(length-1, j)] = A[i]
    return length

INFTY = 10**13
N = int(input())
A = [int(input()) for i in range(N)]
L = [INFTY for i in range(N)]
ans = LISDesc()
print(ans)
print(L)

Submission status: Wrong Answer

Solution code:
import io
import sys


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
5
2
1
4
5
3
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()

  l = []
  pnum = -1
  for i in range(0, n):
    num = IN_I()
    if pnum < num:
      pnum = num
      continue

    # print(l, num)
    for j in range(0, len(l) + 1):
      if j == len(l):
        l.append(pnum)
      else:
        if l[j] < pnum:
          l[j] = pnum
          break

    pnum = num

  if pnum > -1:
    for j in range(0, len(l) + 1):
      if j == len(l):
        l.append(pnum)
      else:
        if l[j] < pnum:
          l[j] = pnum
          break

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Wrong Answer

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

import math

if __name__ == '__main__':
    N = int(input())
    colors = [
        10000000000
    ]
    # R = [0 for i in range(N)]
    # M = 0

    for i in range(N-1, -1, -1):
        # print('i={}'.format(i))
        a = int(input())
        for j in range(len(colors)):
            if a < colors[j]:
                colors[j] = a
                break
        else:
            colors.append(
                a
            )

    print(len(colors))

Submission status: Wrong Answer

Solution code:
import bisect

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

ans = [A[0]]
l = 1
A.reverse()

for i in range(1, N):
    n = bisect.bisect_right(ans, A[i])
    if A[i] >= ans[-1]:
        ans.append(A[i])
    else:
        ans[n] = A[i]

print(len(ans))

Submission status: Wrong Answer

Solution code:
import io
import sys


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
5
2
1
4
5
3
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()

  l = []
  pnum = -1
  for i in range(0, n):
    num = IN_I()
    if pnum < num:
      pnum = num
      continue

    pnum = num
    # print(l, num)
    for j in range(0, len(l) + 1):
      if j == len(l):
        l.append(num)
      else:
        if l[j] < num:
          l[j] = num
          break

  if pnum > -1:
    for j in range(0, len(l) + 1):
      if j == len(l):
        l.append(pnum)
      else:
        if l[j] < pnum:
          l[j] = pnum
          break


  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Wrong Answer

Solution code:
import bisect

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

ans = [A[0]]
l = 1
A.reverse()

for i in range(1, N):
    n = bisect.bisect_left(ans, A[i])
    if A[i] >= ans[-1]:
        ans.append(A[i])
    else:
        ans[n] = A[i]

print(len(ans))

Submission status: Wrong Answer

Solution code:
import io
import sys


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
5
2
1
4
5
3
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()

  l = []
  pnum = 0
  for i in range(0, n):
    num = IN_I()
    if pnum < num:
      pnum = num
      continue

    pnum = num
    # print(l, num)
    for j in range(0, len(l) + 1):
      if j == len(l):
        l.append(num)
      else:
        if l[j] < num:
          l[j] = num
          break

  for j in range(0, len(l) + 1):
    if j == len(l):
      l.append(pnum)
    else:
      if l[j] < pnum:
        l[j] = pnum
        break


  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Wrong Answer

Solution code:
def bisect(arr,val):
  l=-1
  r=len(arr)
  while r-l>1:
    m=(l+r)//2
    if arr[m]<=val:
      r=m
    else:
      l=m
  return r

n=int(input())
arr=[int(input()) for _ in range(n)]
LIS=[arr[0]]
for i in range(1,n):
  if arr[i]<=LIS[-1]:
    LIS.append(arr[i])
  else:
    pos=bisect(LIS,arr[i])
    LIS[pos]=arr[i]
print(len(LIS))

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

def LIS(L):
  L = L[::-1]
  LIS=[L[0]]
  for i in L:
    if i > LIS[-1]:
      LIS.append(i)
    else:
      LIS[bs.bisect_left(LIS,i)]=i
  return len(LIS)

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())
aa = []
co = 0

print(LIS(a))

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

def LIS(L):
  L.sort(reverse = True)
  LIS=[L[0]]
  L.pop()
  for i in L:
    if i >= LIS[-1]:
      LIS.append(i)
    else:
      LIS[bs.bisect_left(LIS,i)]=i
  return len(LIS)

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())
aa = []
co = 0

print(LIS(a))

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect

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

# インデックスの値が増えるにつれて単調増加になる部分は同じ色で良い
# 値が減った時点で違う色が必要になる

# 値を色1リストに追加していく
# 値が減ったら色2リストに値を追加する
# 次の値からは 既存のリストの最大値と比較して、最も差分が小さいリストに追加していく
# ただし、既存のリストの最大値全てよりも小さな値が出てきたらリストを増やして格納する

# 色nリストの最大値だけを持っておくDPリストを作る
# 全て違う色だった場合を考えてN要素のリストにする
# 単調増加にさせたいので後ろから埋めていく
dp = np.zeros(N)
dp[N - 1] = nums[0]
current_head = N - 2
for i in range(1, N):
    # print(f"dp: {dp}")
    current_num = nums[i]
    # 中身がある一番左の値が今の値以上ならば追加する
    if current_num <= dp[current_head + 1]:
        # print(f"追加するよ: {current_num}")
        dp[current_head] = current_num
        # print(dp)
        # 現在の先頭を移動する
        current_head -= 1
        continue
    # それ以外なら追加する場所を探して更新する
    else:
        # print(f"更新するよ: {current_num}")
        # 追加可能な位置 - 1の値を更新する
        # print(dp[current_head + 1 :])
        index = (
            bisect.bisect(dp[current_head + 1 :], current_num) + current_head
        )
        # print(f"index: {index}")
        dp[index] = current_num
        continue

# 中身が入っている先頭の位置から逆算して色の数を出力する
print(N - current_head - 1)

Submission status: Wrong Answer

Solution code:
import bisect
def LIS():
    L[0] = A[0]
    length = 1
    for i in range(1, N):
        print(A[i])
        if L[length-1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

def LISDesc():
    L[0] = A[-1]
    length = 1
    for i in range(N-2, -1, -1):
        if L[length-1] <= A[i]:
            L[length] = A[i]
            length += 1
        else:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
    return length

INFTY = 10**13
N = int(input())
A = [int(input()) for i in range(N)]
L = [INFTY for i in range(N)]
ans = LISDesc()
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)
            
print(len(colors))

Submission status: Wrong Answer

Solution code:
import bisect

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

ans = [A[0]]
l = 1

for i in range(1, N):
    n = bisect.bisect_left(ans, A[i])
    if A[i] >= ans[-1]:
        ans.append(A[i])
    else:
        ans[n] = A[i]

print(len(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))

def LIS(L):
  L.sort(reverse = True)
  seq=[L[0]]
  for i in L:
    if i >= seq[-1]:
      seq.append(i)
    else:
      seq[bs.bisect(seq,i)]=i
  return len(seq)

n = onem()

a = []
c = 0
for i in range(n):
	a.append(onem())
aa = []
co = 0

print(LIS(a))

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

#num:n以上の最小の2のべき乗
num =2**((n-1).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)
    a = [int(input()) for i in range(n)]
    b = sorted(a)
    for i in range(n):
        a[i] = bisect.bisect_left(b,a[i])
    
    tank = [a[0]]
    used[a[0]] = 1
    update(a[0],a[0])
    
    for i in range(1,n):
        while True:
            if used[tank[0]] > 0:
                break
            else:
                heapq.heappop(tank)
        #塗り替え
        if tank[0] < a[i]:
            ma = query(0,a[i])
            
            used[ma] -= 1
            heapq.heappush(tank,a[i])
            used[a[i]] += 1
            if used[ma] == 0:
                update(ma,-1)
        else:
            heapq.heappush(tank,a[i])
            used[a[i]] += 1
        update(a[i],a[i])

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

if __name__ == '__main__':
    main()

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 = max([num for num in nums if num < nn])
    
    # 置き換える
    nums.remove(nums_d)
    nums.append(nn)
    print(nums)
    
print(len(nums))

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = 1
ans = 0
tmp = int(input())
for i in range(1,N):
    A = int(input())
    if A <= tmp:
        memo += 1
    elif ans < memo:
        ans = memo
        memo = 1
    else:
        memo = 1
    tmp = A
    ans = max(ans,memo)
print(ans)

Submission status: Wrong Answer

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

count = 0
temp = []
tempin = []
for i in range(N):
  if i in tempin:
    continue
  temp.append(A[i])
  for j in range(i+1, N):
    if j in tempin:
      continue
    elif temp[-1] < A[j]:
      temp.append(A[j])
      tempin.append(j)
  else:
    print(tempin)
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from collections import OrderedDict

n = int(input())
d = OrderedDict()
d[(int(input()), 0)] = True
i = 1
for a in [int(input()) for _ in range(n - 1)]:
    ((b, j), _) = d.popitem(last=False)
    d[(a, i)] = True
    if b >= a:
        d[(b, j)] = True
    i += 1
print(len(d))

Submission status: Wrong Answer

Solution code:
N = int(input())
a =[0]*(N)
for i in range(N):
  a[i] = int(input())
color = [0]*N
color[0]=a[0]
cnt = a[0]
ans = 1
for i in range(1,N):
    if a[i] <= cnt and a[i] <= color[ans-1]:
        color[ans] = a[i]
        cnt = a[i]
        ans +=1
    elif a[i] <= cnt and a[i] > color[ans-1]:
        color[ans-1] = a[i]
        cnt = a[i]
    else:
        cnt = a[i]
print(ans)

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 == len(result):
        result.append(S[i])
    else:
        result[hoge] = S[i]
print(len(result))

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

#num:n以上の最小の2のべき乗
num =2**((n-1).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])+1
    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)

            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 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)
B=[a]

from bisect import bisect_right as br
from bisect import bisect_left  as bl
from bisect import insort_right as ir
from bisect import insort_left  as il

for i in range(1,N):
	a = int(input())
	A.append(a)
	p("i,a",i,a)
	
#	for j in range(1,len(B)+1):
#		if B[-j]<a:
#			 B[-j]=a
#			 break
#	else:
#		B.append(a)
	
	r = br(B,a)
	l = bl(B,a)
	if r==0 or r==len(B):
		ir(B,a)
	else:
		B[r]=a
		
		

	p("  i, B",i,B)


p("A",A)
p("B",B)

print( len(B) )

Submission status: Wrong Answer

Solution code:
N = int(input())
a =[0]*(N)
for i in range(N):
  a[i] = int(input())
color = [0]*N
color[0]=a[0]
cnt = a[0]
ans = 1
for i in range(1,N):
    if cnt <= a[i] and a[i] <= color[ans-1]:
        color[ans] = a[i]
        cnt = a[i]
        ans +=1
    elif cnt <= a[i] and a[i] > color[ans-1]:
        color[ans-1] = a[i]
        cnt = a[i]
    else:
        cnt = a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


def main():
    N = int(input())
    A = [-int(input()) for _ in range(N)]
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            L.append(a)
        else:
            i = bisect_left(L, a)
            L[i] = a
    print(len(L))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = 1
ans = 0
tmp = int(input())
for i in range(1,N):
    A = int(input())
    if A <= tmp:
        memo += 1
    elif ans < memo:
        ans = memo
        memo = 1
    else:
        memo = 1
    tmp = A
ans = max(ans,memo)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
aa=list(map(int,sys.stdin.read().split()))
aa=aa[1:]
n=len(aa)
import bisect
bb=[]
for i in range(n):
    if not bb:
        bb.append(aa[i])
    else:
        if bb[0] >= aa[i]:
            bb.insert(0, aa[i])
        else:
            j = bisect.bisect_right(bb,aa[i])
            bb[j-1] = aa[i]
print(len(bb))