Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

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

Sample Input 1

5
2
1
4
5
3

Sample Output 1

2

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

Sample Input 2

4
0
0
0
0

Sample Output 2

4

We have to paint all the integers with distinct colors.



Sample input:
5
2
1
4
5
3


Sample output:
2

Submission status: Wrong Answer

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

    print(len(LIS))


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

Submission status: Wrong Answer

Solution code:
from bisect import *

def LIS(N, A):
    L = [0 for i in range(N+1)]
    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:
            # L にA[i]が入る場所を二分探索
            index = bisect_left(L, A[i], 0, length)
            L[index] = A[i]
    return length


N = int(input())
A = [int(input()) for _ in range(N)]
A = A[::-1]
print(LIS(N, A))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left

def bisect_left_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番左側のidxとなる。
    '''
    if a[0] <= x:
        return 0
    if x < a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] <= x:
            ok = mid
        else:
            ng = mid
    return ok

input = sys.stdin.readline
N = int(input())
A = []
for _ in range(N):
	A.append(int(input()))

multi_lis = []
for a_i in A:
    if not multi_lis:
        multi_lis.append(a_i)
        continue

    if a_i <= multi_lis[-1]:
        multi_lis.append(a_i)
    else:
        p = bisect_left_reverse(multi_lis, a_i)
        multi_lis[p] = a_i 

print(len(multi_lis))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
m = 0
cnt = 1
for i in range(1, N):
  if A[i-1] >= A[i]:
    cnt += 1
  else:
    m = max(m, cnt)
    cnt = 1
m = max(cnt, m)
print(m)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# E - Sequence Decomposing
import sys 
from bisect import bisect_left
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,read().split()))


INF = 10**31
q = []

for a in A:
    idx = bisect_left(q, a)
    if idx == 0:
        q.append(a)
    else:
        q[idx-1] = a
print(len(q))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

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

lst = [a[0]]
for aa in a[1:]:
    i = bisect_right(lst, aa)
    if i == len(lst): lst.append(aa)
    else: lst[i] = aa

print(len(lst))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
lst = [a[0]]*2
for aa in a:
    if aa <= lst[0]:
        lst[0] = aa
        ans += 1
    elif lst[0] < aa <= lst[1]:
        lst[0] = aa
    elif aa > lst[1]:
        lst[1] = aa
    else: lst[0] = aa
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
print(a)
ans = 0
lst = [a[0]]*2
for aa in a:
    if aa <= lst[0]:
        lst[0] = aa
        ans += 1
    elif lst[0] < aa <= lst[1]:
        lst[0] = aa
    elif aa > lst[1]:
        lst[1] = aa
    else: lst[0] = aa
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
ans = 0
minai = a[0]
for aa in a:
    if aa <= minai:
        ans += 1
        minai = aa
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input())*N+(N-i-1) for i in range(N)]
A.sort(reverse=True)
for i in range(N):
  A[i] = N - A[i] % N - 1
L = [0 for _ in range(N)]
for i in range(N):
  L[A[i]] = i
m = 0
cnt = 1
for i in range(1, N):
  if L[i-1] < L[i]:
    cnt += 1
  else:
    m = max(m, cnt)
    cnt = 1
m = max(cnt, m)
print(m)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input())*N+(N-i-1) for i in range(N)]
A.sort()
for i in range(N):
  A[i] = N - A[i] % N - 1
L = [0 for _ in range(N)]
for i in range(N):
  L[A[i]] = i
m = 0
cnt = 1
for i in range(1, N):
  if A[i-1] > A[i]:
    cnt += 1
  else:
    m = max(m, cnt)
    cnt = 1
m = max(cnt, m)
print(m)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input())*N+(N-i-1) for i in range(N)]
A.sort()
for i in range(N):
  A[i] = N - A[i] % N - 1
L = [0 for _ in range(N)]
for i in range(N):
  L[A[i]] = i
m = 0
cnt = 1
for i in range(1, N):
  if L[i-1] > L[i]:
    cnt += 1
  else:
    m = max(m, cnt)
    cnt = 1
m = max(cnt, m)
print(m)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
m = float("inf")
for i in range(N):
    x = int(input())
    if m >= x:
        m = x
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque

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

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

for i in range(1, N):
    ind = bisect.bisect_left(dp, A[i])

    if ind == 0:
        dp.appendleft(A[i])
    elif dp[-1] < A[i]:
        dp[-1] = A[i]
    else:
        dp[ind] = A[i]

print(len(dp))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

# reffer to: https://qiita.com/dn6049949/items/afa12d5d079f518de368
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.data = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        while i > 0:
            i >>= 1
            self.data[i] = self.f(self.data[i*2], self.data[i*2+1])

    # [l, r)
    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.data[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


def main():
    N = I()
    A = IR(N)

    LDS = [-A[0]]
    for ai in A[1:]:
        if -LDS[-1] >= ai:
            LDS.append(-ai)
        else:
            LDS[bisect_left(LDS, -ai)] = -ai

    print(len(LDS))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  _l=[I() for _ in range(n)]
  l=collections.deque()

  for A in _l:
    if len(l)==0:
      l.append(A)
      continue

    lv=l[0]
    rv=l[-1]
    if rv<A:
      l[-1]=A
      continue
    if A<=lv:
      l.appendleft(A)
      continue

    li=0
    ri=len(l)-1
    while ri-li>1:
      mi=(ri+li)//2
      if l[mi]<A:
        ri=mi
      else:
        li=mi

    l[li]=A

  # print(l)
  return len(l)

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  _l=[I() for _ in range(n)]
  l=collections.deque()

  for A in _l:
    if len(l)==0:
      l.append(A)
      continue

    lv=l[0]
    rv=l[-1]
    if rv<A:
      l[-1]=A
      continue
    if A<=lv:
      l.appendleft(A)
      continue

    li=0
    ri=len(l)-1
    while ri-li>1:
      mi=(ri+li)//2
      if l[mi]>A:
        ri=mi
      else:
        li=mi

    l[li]=A

  # print(l)
  return len(l)

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  _l=[I() for _ in range(n)]
  l=collections.deque()

  for A in _l:
    if len(l)==0:
      l.append(A)
      continue

    lv=l[0]
    rv=l[-1]
    if rv<A:
      l[-1]=A
      continue
    if A<=lv:
      l.appendleft(A)
      continue
    if rv==A:
      l.append(A)
      continue

    li=0
    ri=len(l)-1
    while ri-li>1:
      mi=(ri+li)//2
      if l[mi]>A:
        ri=mi
      else:
        li=mi

    l[li]=A

  # print(l)
  return len(l)

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  _l=[I() for _ in range(n)]
  l=[]

  for A in _l:
    if len(l)==0:
      l.append([A])
      continue

    lv=l[0][-1]
    rv=l[-1][-1]
    if rv<A:
      l[-1].append(A)
      continue
    if A<=lv:
      l=[[A]]+l
      continue
    if rv==A:
      l.append([A])
      continue


    li=0
    ri=len(l)-1
    while ri-li>1:
      mi=(ri+li)//2
      if l[mi][-1]>A:
        ri=mi
      else:
        li=mi

    l[li].append(A)

  # print(l)
  return len(l)

# main()
print(main())

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(input())]
for i in range(N-1):
  a=int(input())
  if a<=min(A):
    A.append(a)
  elif a>=max(A):
    A[0]=a
  else:
    for j,ls in enumerate(A[::-1]):
      if ls>=a:
        A[-j]=a
        break
print(len(A))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
used_color = 0
used_color_min = float("inf")
for i in range(n):
    if used_color_min >= a[i]:
        used_color += 1
        used_color_min = a[i]
print(used_color)

Submission status: Wrong Answer

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

LIS = [a[0]]
for v in a[1:]:

    if LIS[-1] <= v:
        LIS.append(v)
    else:
        LIS[bisect_left(LIS, v)] = v
 
print(len(LIS))

Submission status: Wrong Answer

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

LIS = [a[0]]
for v in a:
    if LIS[-1] < v:
        LIS.append(v)
    else:
        LIS[bisect_left(LIS, v)] = v
 
print(len(LIS))

Submission status: Wrong Answer

Solution code:
def lis(arr):
    n = len(arr)
    # dp
    lis = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    
    maximum = 0
    for i in range(n):
        maximum = max(maximum, lis[i])
    
    return maximum

n=int(input())
a=[int(input())*(-1) for i in range(n)]

print(lis(a))

Submission status: Wrong Answer

Solution code:
def lis(arr):
    n = len(arr)
    # dp
    lis = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    
    maximum = 0
    for i in range(n):
        maximum = max(maximum, lis[i])
    
    return maximum

n=int(input())
a=[int(input())*(-1) for i in range(n)]

print(lis(a))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
for _ in range(n):
    a = int(input())
    A.append(a)
ans = 0
tmp = 1
if n==1:print(1);exit()
for i in range(n-1):
    if A[i]>=A[i+1]:
        tmp += 1
    else:
        tmp = 1
    ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = []
for _ in range(n):
    a = int(input())
    A.append(a)
ans = 0
tmp = 1
if n==1:print(1);exit()
for i in range(n-1):
    if A[i]>=A[i+1]:
        tmp += 1
        ans = max(ans,tmp)
    else:
        tmp = 1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    ans = 0
    now = 1
    for i in range(1, n):
        if a[i - 1] < a[i]:
            ans = max(ans, now)
            now = 1
        else:
            now += 1
    ans = max(ans, now)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heapify, heappush
from collections import Counter


def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    cnt_a = max(Counter(a).values())
    max_q = [-a[0]]
    min_q = [a[0]]
    heapify(max_q)
    heapify(min_q)
    ans = 1
    for i in range(1, n):
        now_max = -heappop(max_q)
        now_min = heappop(min_q)
        if a[i] <= now_min:
            heappush(min_q, now_min)
            now_min = a[i]
            ans += 1
        elif now_max == a[i]:
            heappush(max_q, -now_max)
            ans += 1
        elif now_max < a[i]:
            now_max = a[i]
        heappush(max_q, -now_max)
        heappush(min_q, now_min)
    print(ans if cnt_a == 1 else cnt_a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heapify, heappush


def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    max_q = [-a[0]]
    min_q = [a[0]]
    heapify(max_q)
    heapify(min_q)
    ans = 1
    for i in range(1, n):
        now_max = -heappop(max_q)
        now_min = heappop(min_q)
        if a[i] <= now_min:
            now_min = a[i]
            ans += 1
        elif now_max <= a[i]:
            now_max = a[i]
        heappush(max_q, -now_max)
        heappush(min_q, now_min)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
INF=10**18
n=int(input())
a=[int(input()) for _ in range(n)][::-1]
dp=[INF]
for i in a:
  if i>=dp[-1]:dp+=[i]
  else:dp[bisect.bisect_left(dp,i)]=i
print(len(dp))

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect
N=int(input())
L=deque()
for i in range(N):
  s=int(input())
  if i==0:
    L.append(s)
  else:
    if s<=L[0]:
      L.appendleft(s)
    else:
      L[bisect.bisect(L,s)-1]=s
print(len(L))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    min_a = 10**9 + 1
    ans = 0
    for i in range(N):
        tmp = int(input())
        if tmp <= min_a:
            ans += 1
            min_a = tmp
    print(ans)








main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 0
Min = float('inf')
for i in range(n):
    a = int(input())
    if a <= Min:
        ans += 1
        Min = a
print(ans)

Submission status: Wrong Answer

Solution code:
count=1
n=int(input())
mina=int(input())
for _ in range(n-1):
    a=int(input())
    if mina>=a:
        count+=1
        mina=a
print(count)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    D = [float('inf')]*N
    res = [0]*N
    for i in range(N):
        num = I()
        index = bisect_left(D, num)
        D[index] = num
        res[index]+=1
    print(max(res))




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    max_num = float('inf')
    D = [max_num]
    heapify(D)
    for i in range(N):
        if i == 0:
            D[0] = I()
        else:
            num = I()
            index = bisect_left(D, num)
            if index == 0:
                heappush(D, num)
            else:
                D[index-1] = num


    print(len(D))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    ans = [-int(ipt())]
    for i in range(n-1):
        a = -int(ipt())
        if a >= ans[-1]:
            ans.append(a)
        else:
            ans[bisect.bisect_left(ans,a)] = a

    print(len(ans))

    return None

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
    p = int(input())
    a.append(p)
q = 0
ans = 0
a.reverse()
s = a[0]
for i in range(n-1):
    if a[i] <= a[i+1]:
        q += 1
    else:
        ans = max(ans,q)
        q = 0
ans = max(ans,q)
print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import bisect_left
N=int(input())
d=deque()
for i in range(N):
    A=int(input())
    b=bisect_left(d,A)-1
    if b==-1:
        d.appendleft(A)
    else:
        d[b]=A
print(len(d))
print(d)

Submission status: Wrong Answer

Solution code:
import bisect

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

print(len(LIS))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)
AA = set(A)
count = 1
b = A[-1]
for i in reversed(range(N-1)):
    if A[i]>b:
        b = A[i]
        count+=1
        
        
        
print(count+len(A)-len(AA))

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
A = list(int(input()) for _ in range(N))

S = [A[0]]
for i in range(1, N):
    if A[i] <= S[0]:
        S.insert(0, A[i])
        continue
    ok = 0
    ng = len(S)
    tmp = (ok+ng)//2
    while ok+1 < ng:
        tmp = (ok+ng)//2
        if A[i] > S[tmp]:
            ok = tmp
        else:
            ng = tmp
    S[tmp] = A[i]
print(len(S))

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
A = list(int(input()) for _ in range(N))

S = [A[0]]
for i in range(1, N):
    if A[i] <= S[0]:
        S.insert(0, A[i])
        continue
    for j in range(len(S)):
        if A[i] < S[j]:
            S[j-1] = A[i]
            break
    else:
        S[-1] = A[i]
print(len(S))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
for i in range(N):
  a=int(input())
  A.append(a)
B=[]
m=1
c=1
for i in range(N-1):
  if A[i+1]<=A[i] and i!=N-2:
    c+=1
  if A[i+1]>A[i] and i!=N-2:
    m=max(c,m)
    c=0
  if A[i+1]<=A[i] and i==N-2:
    c+=1
    m=max(c,m)
  if A[i+1]>A[i] and i==N-2:
    m=max(c,m)
print(m)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
N = int(input())
seq = [0] * N
for i in range(N):
  seq[i] = (-1) * int(input())

#リストseqからLISの長さを出す
LIS = [seq[0]]
for i in range(len(seq)):
    if seq[i] >= LIS[-1]:
        LIS.append(seq[i])
    else:
        LIS[bisect_right(LIS, seq[i])] = seq[i]

print(len(LIS) - 1)
#print(LIS)

Submission status: Wrong Answer

Solution code:
# AtCoder Beginner Contest 134 E - Sequence Decomposing

import sys
import bisect

N = int(input())
now = int(sys.stdin.readline().strip())
ans = [now]

for n in range(N - 1):
    now = int(sys.stdin.readline().strip())

    if now > ans[0]:
        ans[0] = now
    elif ans[-1] >= now:
        ans.append(now)
    else:
        # 2部探査で行進位置を探る
        left = 0  # 挿入不可能
        right = len(ans) - 1  # 挿入可能

        while right - left > 1:
            mid = (right + left) // 2
            if ans[mid] > now:
                right = mid
            else:
                left = mid

        ans[right] = now

print(len(ans))

    # if ans:  # 最初の入力以外であり、すでに追加対象のリストが存在する
    #     if ans[0][-1] < now:
    #         ans[0].append(now)
    #     elif ans[-1][-1] >= now:
    #         appending = [now]
    #         ans.append(appending)
    #     else:
    #         # 二分探索で追加するリストの位置を特定する
    #         left = 0   # 追加できない  ans[left][-1] > now
    #         right = len(ans) - 1  # ans[right][-1] < now
    #
    #         while right - left > 1:
    #             mid = (right - left) // 2
    #             if ans[mid][-1] < now:
    #                 right = mid
    #             else:
    #                 left = mid
    #         ans[right].append(now)
    # else:
    #     appending = [now]
    #     ans.append(appending)

    # for a in ans:
    #     if a[-1] < now:
    #         a.append(now)
    #         break
    # else:
    #     appending = [now]
    #     ans.append(appending)

# print(len(ans))

Submission status: Wrong Answer

Solution code:
def LIS(A):
    dp = [-A[0]]
    for a in A[1:]:
        if -a >= dp[-1]:
            dp.append(-a)
        else:
            dp[bisect_left(dp, -a)] = -a
    return len(dp)

##################################################################################################################

import sys
input = sys.stdin.readline
from bisect import bisect_left

N = int(input())

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

print(LIS(A))

Submission status: Wrong Answer

Solution code:
def LIS(A):
    dp = [-A[0]]
    for a in A[1:]:
        if -a >= dp[0]:
            dp.append(-a)
        else:
            dp[bisect_left(dp, -a)-1] = -a
    return len(dp)

##################################################################################################################

import sys
input = sys.stdin.readline
from bisect import bisect_left

N = int(input())

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

print(LIS(A))

Submission status: Wrong Answer

Solution code:
def LIS(A):
    dp = [A[0]]
    for a in A[1:]:
        if a > dp[-1]:
            dp.append(a)
        else:
            dp[bisect_left(dp, a)-1] = a
    print(dp)
    return len(dp)

##################################################################################################################

import sys
input = sys.stdin.readline
from collections import deque
from bisect import bisect_left

N = int(input())

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

print(LIS(A))

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 num>=DP[-1]:
        DP.append(num)
    else:
        index=bisect_left(DP,num)
        DP[index]=num
print(len(DP))

Submission status: Wrong Answer

Solution code:
n = int(input())
t = 1000_000_000_3
ans = 1
a = int(input())
for _ in range(n-1):
    a1 = int(input())
    if a1 > a:
        a = a1
    else:
        if t >= a1:
            t = a1
            ans += 1
            a = a1
        else:
            t =  a1
            a = a1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
colors = [int(input())]
for _ in range(n-1):
    a = int(input())
    i = bisect.bisect_right(colors, -a)
    if i == len(colors):
        colors.append(-a)
    else:
        colors[i] = -a
print(len(colors))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def LIS(arr):  #bisect.bisect_left
    n = len(arr)
    lis = [-10**18]
    for a in arr:
        if a >= lis[-1]:
            lis.append(a)
        else:
            lis[bisect_left(lis, a)] = a
    return len(lis) - 1

import sys
input = sys.stdin.readline

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

print(LIS(A))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def LIS(arr):  #bisect.bisect_left
    n = len(arr)
    lis = [10**18]
    for a in arr:
        if a >= lis[-1]:
            lis.append(a)
        else:
            lis[bisect_left(lis, a)] = a
    return len(lis)

import sys
input = sys.stdin.readline

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

print(LIS(A))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def LIS(arr):  #bisect.bisect_left
    n = len(arr)
    lis = [arr[0]]
    for a in arr:
        if a >= lis[-1]:
            lis.append(a)
        else:
            lis[bisect_left(lis, a)] = a
    return len(lis)

import sys
input = sys.stdin.readline

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

print(LIS(A) - 1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right

def solve(arr):  #bisect.bisect_left
    n = len(arr)
    lis = [arr[0]]
    for a in arr:
        if a >= lis[-1]:
            lis.append(a)
        else:
            lis[bisect_right(lis, a)] = a
    return len(lis) - 1

import sys
input = sys.stdin.readline

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

print(solve(A))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_right
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(int(readline()) for _ in range(N))

    LIS = [INF]*N
    A.reverse()
    for a in A:
        i = bisect_right(LIS,a)
        LIS[i] = a
    print(bisect_right(LIS, INF))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(int(readline()) for _ in range(N))

    LIS = [INF]*(N+1)
    count = 0
    for a in A:
        i = bisect_left(LIS,a)
        if i==0:
            count += 1
        LIS[i] = a
    print(count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from bisect import insort_right, bisect_right

N = int(input())
A = []
for _ in range(N):
    x = int(input())
    idx = bisect_right(A, x)
    if idx == 0:
        A = [x] + A
    else:
        if A[idx-1]==x:
            insort_right(A, x)
        A[idx-1] = x
#    print(A)
print(len(A))

Submission status: Wrong Answer

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

from bisect import insort_left, bisect_right

N = int(input())
A = []
for _ in range(N):
    x = int(input())
    idx = bisect_right(A, x)
    if idx == 0:
        A = [x] + A
    else:
        if A[idx-1]==x:
            insort_left(A, x)
        A[idx-1] = x
#    print(A)
print(len(A))