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 i in range(n):
  ai=int(input())
  a.append(ai)
b=[a[n-1]]
for i in reversed(range(n-1)):
  if a[i]>=b[-1]:
    b.append(a[i])
  else:
    for j in b:
      if j>a[i]:
        j=a[i]
        break
print(len(b))

Submission status: Wrong Answer

Solution code:
n = int(input())
color = [int(input())]
for _ in range(n-1):
  key = int(input())
  if key <= color[0]:
    color.append(key)
  else:
    l, r = 0, len(color)
    while r-l > 1:
      k = (r+l)//2
      if key <= color[k]:
        l = k
      else:
        r = k
    if l == 0:
      if r == len(color):
        pass
      elif key > color[r]:
        l = r
    color[l] = key
  color.sort()
print(len(color))

Submission status: Wrong Answer

Solution code:
import bisect

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

l = [alist[0],]
if n > 1:
  for a in alist[1:]:
    if l[-1] < a:
      l[-1] = a
    else:
      if l[0] >= a:
        l = [a] + l
      else:
        pos = bisect.bisect_right(l, a)
        l[pos-1] = a
print(len(l))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input()) for _ in range(N)]
mi=A[0]
cnt=1
for i in range(1,N):
    if A[i]<=mi:
        mi=A[i]
        cnt=cnt+1
print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n=int(input())
A=[int(input()) for _ in range(n)][::-1]

DP=[A[0]]
for i in range(1,n):
    num=A[i]
    if DP[-1]<=num:
        DP.append(num)
    else:
        index=bisect_left(DP,num)
        DP[index]=num
print(len(DP))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n=int(input())
A=[-int(input()) for _ in range(n)]

DP=[A[0]]
for i in range(1,n):
    num=A[i]
    if DP[-1]<=num:
        DP.append(num)
    else:
        index=bisect_left(DP,num)
        DP[index]=num
print(len(DP))

Submission status: Wrong Answer

Solution code:
n=int(input())
color_list=[[] for _ in range(n+1)]
color_list[1].append(int(input()))
max_color=1
for i in range(n-1):
  a=int(input())
  max_index=0
  max_number=0
  for j in range(1,max_color+1):
    if color_list[j][-1]<a:
      if color_list[j][-1]>max_index:
        max_index=j
        max_number=color_list[j][-1]
  if max_index==0:
    max_color+=1
    color_list[max_color].append(a)
  else:
    color_list[max_index].append(max_number)
print(max_color)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
for i in range(N):
	L.append(int(input()))
count=1
j=N-1
i=0
M=1
ans=1
for i in range(N-1):
	if L[i]<L[i+1]:
		ans=max(ans,M)
		M=1
	else:
		M+=1
ans=max(ans,M)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
for i in range(N):
	L.append(int(input()))
count=1
j=N-1
i=0
M=1
ans=1
for i in range(N-1):
	if L[i]<L[i+1]:
		ans=max(ans,M)
		M=0
	else:
		M+=1
ans=max(ans,M)
print(ans)

Submission status: Wrong Answer

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

import bisect
from collections import deque

q = deque([])
for i, Ai in enumerate(A):
    if i == 0:
        ans = 1
        q.append(Ai)
        continue
    #
    idx = bisect.bisect_left(q, Ai)
    if idx == 0:
        q.appendleft(Ai)
    else:
        q[min(idx + 1, len(q) - 1)] = Ai
    #
    # print("#", q, ans)

print(len(q))

Submission status: Wrong Answer

Solution code:
N=int(input())
L=[]
for i in range(N):
	L.append(int(input()))
count=1
j=N-1
i=0
while(1):
	#print(count,i,j)
	if i==j:
		break
	elif L[i]<L[j]:
		i+=1
	else:
		j-=1
		count+=1
print(count)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import heapq
n = int(input())
x = [int(input())]
heapq.heapify(x)
for _ in range(n-1):
  a = int(input())
  if a <= x[0]:
    heapq.heappush(x, a)
  else:
    x.pop(bisect_left(x, a)-1)
    heapq.heappush(x, a)
print(len(x))

Submission status: Wrong Answer

Solution code:
from bisect import*
N=int(input())
ans=[]
cnt=0
for i in range(N):
    a=int(input())
    l=bisect_left(ans,a)
    r=bisect_right(ans,a)
    if l==0:
        ans.insert(0,a)
    elif ans[r-1]==a:
      ans.insert(r,a)
    else:
      ans[r-1]=a
print(len(ans))

Submission status: Wrong Answer

Solution code:
from bisect import*
N=int(input())
ans=[]
cnt=0
for i in range(N):
    a=int(input())
    if bisect_left(ans,a)==0:
        ans.insert(0,a)
    else:
        ans[bisect_right(ans,a)-1]=a
print(len(ans))

Submission status: Wrong Answer

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

cnt = 0

while len(a)>0:
    a_l = a.pop(0)
    for i in range(len(a)-1,-1,-1):
        if a[i] > a_l:
            a_r = a.pop(i)
    for j in range(len(a)-1,-1,-1):
        if a_l < a[j] < a_r:
            a_r = a.pop(j)
            
    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[]
A=A[::-1]
for a in A:
    i=bisect.bisect_left(color,a)
    if i==len(color):
        color.append(a)
    else:
        color[i]=a
print(len(color))

Submission status: Wrong Answer

Solution code:
def Binary_Search(list,item):
    low=0
    high=len(list)-1
    while low<=high :
        mid=(high+low)//2
        if item <= list[mid]:
            high=mid-1
        else:
            low=mid+1
    return low


N=int(input())
A=[int(input()) for _ in range(N)]
color=[A[-1]]
A=A[::-1]
for x in range(1,N):
    a=A[x]
    i=Binary_Search(color,a)
    if i==len(color):
        color.append(a)
    else:
        color[i]=a
print(len(color))

Submission status: Wrong Answer

Solution code:
import heapq
def Binary_Search(list,item):
    low=0
    high=len(list)-1
    while low<=high :
        mid=(high+low)//2
        if item <= list[mid]:
            high=mid-1
        else:
            low=mid+1
    return high

color=[]
N=int(input())
a=int(input())
heapq.heappush(color,a)
cnt=1
for _ in range(N-1):
    a=int(input())
    if a<=color[0]:
        heapq.heappush(color,a)
        cnt+=1
    else:
        color[Binary_Search(color,a)]=a
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)


class Node:
    def __init__(self, data): #コンストラクタ
        self.data = data #ノードがもつ数値
        self.left = None #左エッジ
        self.right = None #右エッジ
N = int(input())
A = [int(input()) for i in range(N)]
G = [Node(A[0])]
def rec(g,ni):
    if g.data < ni.data:
        if g.right is None:
            g.right = ni
        else:
            rec(g.right,ni)
    else:
        if g.left is None:
            g.left = ni
        else:
            rec(g.left,ni)

for i in range(1,N):
    Ni = Node(A[i])
    rec(G[0],Ni)
    G.append(Ni)
ans = 1
g = G[0]
while True:
    if g.left is None:
        break
    else:
        g = g.left
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:

N = int(input())
A = [int(input()) for i in range(N)]
now = A[0]
ans = 1
for i in range(1,N):
    if now < A[i]:
        continue
    else:
        now = A[i]
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

f_inf = float("inf")
n = int(input())
A = [int(input()) for _ in range(n)][::-1]
dp = [f_inf for _ in range(n + 1)]

for a in A:
    idx = bisect.bisect_left(dp, a)
    dp[idx] = a

ans = bisect.bisect_left(dp, f_inf)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(input()) for i in range(n)]
m = 10**9
c = 0
for a in A:
    if a <= m:
        c += 1
        m = a
print(c)

Submission status: Wrong Answer

Solution code:
def resolve():
    import heapq
    n = int(input())
    a = [int(input()) for i in range(n)]
    maxlist = [-1 * a[n-1]]
    heapq.heapify(maxlist)
    for i in range(n-2, -1, -1):
        maxel = heapq.heappop(maxlist)
        if -1 * a[i] > maxel:
            heapq.heappush(maxlist, -1*a[i])
        elif -1 * a[i] <= maxel:
            heapq.heappush(maxlist, -1 * a[i])
            heapq.heappush(maxlist, maxel)
    print(len(maxlist))
resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(input()) for i in range(n)]
m = 10**9
c = 0
for a in A:
    if a <= m:
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
import bisect

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


seq = A

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

print(len(LIS)-1)

Submission status: Wrong Answer

Solution code:
from queue import deque
n = int(input())
a = deque([int(input()) for _ in range(n)])
point = 0
while len(a) >= 2:
    point += 1
    li = []
    now = a.popleft()
    for i in range(1,len(a)+1):
        j = a.popleft()
        if j <= now:
            li += [j]
    a = deque(li[:])
if a:
    point += 1
print(point)

Submission status: Wrong Answer

Solution code:
import bisect
import sys

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

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


def check(cnt_color: int) -> bool:

    cols = [A[0]]
    min_cols = A[0]

    for ai in A[1:]:
        if ai <= min_cols:
            cols = [ai] + cols
            min_cols = ai
            if len(cols) > cnt_color:
                return True
            continue
        idx = bisect.bisect(cols, ai)
        cols[idx-1] = ai
    return False


high = N  # 必ず条件を満たす
low = 0    # 必ず条件を満たさない
while high - low > 1:
    mid = (high + low) // 2
    if check(mid):
        low = mid
    else:
        high = mid

print(high)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque

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

d = deque()
d.append(a[-1])
for i in reversed(range(N-1)):
	if a[i] >= d[-1]:
		d.append(a[i])
	else:
		index = bisect.bisect_left(d,a[i])
		d[index] = a[i]

print(len(d))

Submission status: Wrong Answer

Solution code:
import bisect

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

ans = 0
num = 10**9+7
LIS = [a[0]]
for i in range(N):
    if a[i] > LIS[-1]:
        LIS.append(a[i])
    else:
    	if num >= a[i]:
    		ans += 1
    		num = a[i]
    		#print(num)
    	LIS[bisect.bisect_left(LIS, a[i])] = a[i]

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

for l in L:
    if len(Q) == 0:
        Q.append(l)
    else:
        Q = sorted(Q)
        r = bisect.bisect_left(Q, l)
        if r == 0:
            Q.append(l)
            Q = sorted(Q)
        else:
            Q[-1] = l
print(len(Q))

Submission status: Wrong Answer

Solution code:
n = int(input())

c = []
for i in range(n):
    a = int(input())
    v = 0
    k = -1
    for j in range(len(c)):
        if v < c[j][-1] < a:
            v = c[j][-1]
            k = j
    if k < 0:
        c.append([a])
    else:
        c[k].append(a)
print(len(c))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a1 = int(input())
a = [a1]
for _ in range(n-1):
  ai = int(input())
  if ai <= a[-1]:
    a.append(ai)
  elif ai >= a[0]:
    a = [ai]+a[1:]
  else:
    h = 0
    l = len(a)-1
    while l-h>1:
      m = (l+h)//2
      if ai > a[m]:
        l = m
      else:
        h = m
    a = a[:l]+[ai]+a[l+1:]
print(len(a))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
for i in range(n):
  A.append(int(input()))
m = n
t = 0
B = [0]
while B != []:
  B = []
  for i in range(m-1):
    if A[i] >= A[i+1]:
      B.append(A[i+1])
  A = B
  t += 1
  m = len(B)
print(t)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = []
    for i in range(N):
        A.append(iip(False))

    maxes = [-1]
    nc = 1
    for a in A:
        idx = bisect_right(maxes, a)
        if idx == nc:
            maxes.append(a)
            nc += 1
        else:
            maxes[idx] = a

    print(nc)

#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = []
    for i in range(N):
        A.append(iip(False))

    maxes = [-1]
    nc = 1
    for a in A:
        if maxes[0] >= a: #使い回せる色がなければ新色追加
            maxes.append(a)
            nc += 1
            continue

        idx = bisect_left(maxes, a-1)
        if idx >= nc:
            idx = nc-1
        maxes[idx] = a


    print(nc)

#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = []
    for i in range(N):
        A.append(iip(False))

    maxes = [-1]
    nc = 1
    for a in A:
        if maxes[0] >= a: #使い回せる色がなければ新色追加
            insort_left(maxes, a)
            nc += 1
            continue

        idx = bisect_left(maxes, a-1)
        if idx >= nc:
            idx = nc-1
        maxes[idx] = a


    print(nc)

#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N = iip(False)
    A = []
    for i in range(N):
        A.append(iip(False))

    maxes = [-1]
    nc = 1
    for a in A:
        if maxes[0] >= a: #使い回せる色がなければ新色追加
            insort_left(maxes, a)
            nc += 1
            continue


        idx = bisect_left(maxes, a-1)
        if idx >= nc:
            idx = nc-1
        #print(a, idx)
        #print(maxes)
        maxes.pop(idx)
        insort_left(maxes, a)
        #print(maxes)

    print(nc)

#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N = int(input())
A = [int(input()) for _ in range(N)]
Min = [A[-1]]
for i in range(N-2, -1, -1):
    temp = bisect.bisect_left(Min, A[i])
    if temp == len(Min):
        Min.append(A[i])
    elif Min[temp] != A[i]:
        Min[temp] = A[i]
    else:
        Min.append(A[i])
print(len(Min))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N = int(input())
check = [0]*(N+1)
A = [int(input()) for _ in range(N)]
LIS = [INF]*(N+1)
for i in range(N):
    temp = bisect.bisect_left(LIS, A[i])
    check[temp] += 1
    LIS[temp] = A[i]
print(max(check))

Submission status: Wrong Answer

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

dp = [10**10] * N

for a in A:
    dp[bisect_right(dp, a)] = a

print(dp.count(10**10))

Submission status: Wrong Answer

Solution code:
#134_E
import bisect
n=int(input())
a=[int(input()) for _ in range(n)][::-1]

LIS = [a[0]]
for i in range(1, n):
    if a[i] >= LIS[-1]:
        LIS.append(a[i])
    else:
        LIS[bisect.bisect_left(LIS, a[i])] = a[i]

print(len(LIS))

Submission status: Wrong Answer

Solution code:
#134_E
n=int(input())
a=[int(input()) for _ in range(n)][::-1]

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

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
for i in range(n):
    a = int(input())
    A.append(a)
A_rev = A[::-1]
cnt = 0
tmp = 0
for i in range(n):
    if i==0:
        tmp = A_rev[i]
        cnt += 1
    elif A_rev[i] >= tmp:
        tmp = A_rev[i]
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
ans = [-1*int(input())]
for i in range(n-1):
  a=int(input())
  a=-1*a
  if ans[-1]<=a:
    ans.append(a)
  else:
    b = bisect.bisect_left(ans,a)
    ans[b]=a
print(len(ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
ans=[]
m=10**10
for i in range(0,N):
    a=int(input())
    if m>=a:
        ans.append(a)
        m=a
    else:
        start=0
        end=len(ans)-1
        while end-start>1:
            test=(end+start)//2
            if a>ans[test]:
                end=test
            else:
                start=test
        if a>ans[end]:
            ans[end]=a
            if end==0:
                m=a
        else:
            ans[start]=a
            if start==0:
                m=a

print(len(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
X = [A[0]]
for i in range(1, N):
    flag = False
    for x in X:
        if x < A[i]:
            flag = True
    if not flag:
        X.append(A[i])
print(len(X))

Submission status: Wrong Answer

Solution code:
#
#  |    X| | |
#  |  X X| | |
#  |  X X|X|X|X
# X|  X X|X|X|X
# X|X X X|X|X|X
# 2,1,4,5,3,3,3
# R G G G R B Y | R=2, G=1,4,5, R(2回目!)=3, Y=3 
# reverse
# 3 3 3 5 4 1 2
# 1 2 3 4 4 4 🐓 | d = {1:[3], 2:[3], 3:[3], 4:[5,4,1]} で覚えておけば 1->2の色変えで古いやつを使える の判定で良い???? 
n = int(input())
l = []
for i in range(n):
    l.append(int(input()))
l = l[::-1]
l = [9999999999] + l
d = {0:[l[0]]}
mmmax = -1
current_color = 0
for i in range(1,len(l)):
    new_color = True
    if l[i] < d[current_color][-1]:
        color = current_color
        hoges = d[color]
        hoges.append(l[i])
        d[color] = hoges
        new_color = False
        current_color = color
    elif l[i] > mmmax:
        mmax = l[i]
        for color in range(min(100, len(d))):  # [0, 0, ,,,0] => 1e5 * 1e5 なのでTLE
            hoges = d[color]
            if l[i] < hoges[-1]:
                hoges.append(l[i])
                d[color] = hoges
                new_color = False
                current_color = color
                break
    if new_color:
        color = len(d)
        current_color = color
        d[color] = [l[i]]
print(len(d))

Submission status: Wrong Answer

Solution code:
#
#  |    X| | |
#  |  X X| | |
#  |  X X|X|X|X
# X|  X X|X|X|X
# X|X X X|X|X|X
# 2,1,4,5,3,3,3
# R G G G R B Y | R=2, G=1,4,5, R(2回目!)=3, Y=3 
# reverse
# 3 3 3 5 4 1 2
# 1 2 3 4 4 4 🐓 | d = {1:[3], 2:[3], 3:[3], 4:[5,4,1]} で覚えておけば 1->2の色変えで古いやつを使える の判定で良い???? 
n = int(input())
l = []
for i in range(n):
    l.append(int(input()))
l = l[::-1]
l = [9999999999] + l
d = {0:[l[0]]}
mmmax = -1
current_color = 0
for i in range(1,len(l)):
    new_color = True
    if l[i] < d[current_color][-1]:
        color = current_color
        hoges = d[color]
        hoges.append(l[i])
        d[color] = hoges
        new_color = False
        current_color = color
    elif l[i] > mmmax:
        mmax = l[i]
        for color in range(min(1, len(d))):  # [0, 0, ,,,0] => 1e5 * 1e5 なのでTLE
            hoges = d[color]
            if l[i] < hoges[-1]:
                hoges.append(l[i])
                d[color] = hoges
                new_color = False
                current_color = color
                break
    if new_color:
        color = len(d)
        current_color = color
        d[color] = [l[i]]
print(len(d))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

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

s = deque([a[0]])

from bisect import bisect_right

for i in a[1:]:
    if i <= s[0]:
        s.appendleft(i)
    else:
        s[bisect_right(s, i) - 1] = i

# print(s)
print(len(s))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

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

s = deque([a[0]])

from bisect import bisect_right

for i in a[1:]:
    if i <= a[0]:
        s.appendleft(i)
    else:
        s[bisect_right(s, i) - 1] = i

# print(s)
print(len(s))