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:
from bisect import bisect_left
N = int(input())
A = [int(input()) for i in range(N)]
A.reverse()
X = [A[0]]

for i in range(1, N):
    if X[-1] <= A[i]:
        X.append(A[i])
    else:
        idx = bisect_left(X, A[i])
        X[idx] = A[i]

print(len(X))

Submission status: Wrong Answer

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

for i in range(1, N):
    if X[0] >= A[i]:
        X.insert(0, A[i])
    else:
        idx = bisect_right(X, A[i])
        X[idx-1] = A[i]

print(len(X))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#import sys
#def input(): return sys.stdin.readline().strip()

from bisect import bisect

icase=1
if icase==1:
    n=int(input())
    a=[0]*n
    for i in range(n):
        a[i]=-int(input())
elif icase==2:
    n=5
    a=[-2,-1,-4,-5,-3]

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -1
    
#    print(n,a,dp)
    for i in range(n):
        idx = bisect(dp, a[i]-1)
        dp[idx] = min(a[i], dp[idx])

#        print("i:",i,"a:",a,"dp2:",dp2)            
    return dp

dp=loopa()        

print(bisect(dp, 10**10-1))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(int(input()) for _ in range(n))

    que = deque([A[0]])
    for i in range(1, n):
        if que[-1] < A[i]:
            que[-1] = A[i]
        elif que[0] < A[i]:
            que[0] = A[i]
        else:
            que.appendleft(A[i])
    print(len(que))


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
n = int(input())
old = -1
cnt = 1
up = False
for i in range(n):
  a = int(input())
  if i == 0:
    old = a
    continue
  if a <= old:
    if not up:
      cnt += 1
      up = False
  else:
    up = True
  old = a
print(cnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

icase=0
if icase==0:
    n=int(input())
    a=[0]*n
    for i in range(n):
        a[i]=int(input())

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -1
    dq = [0]*(n+1)    
    
    for i in range(n):
        idx = bisect(dp, a[i]-1)
        if dp[idx]==10**10:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i
#            dp2=dp[1:idx+1]
            dq2=dq[1:idx+1]
        else:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i

    dq2.sort() 
    for i in range(len(dq2)-1,-1,-1):
        del a[dq2[i]]

icnt=0
while len(a)>0:
    loopa()        
    icnt+=1

print(icnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

icase=0
if icase==0:
    n=int(input())
    a=[0]*n
    for i in range(n):
        a[i]=int(input())

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -1
    dq = [0]*(n+1)    
    
    for i in range(n):
        idx = bisect(dp, a[i]-1)
        if dp[idx]==10**10:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i
#            dp2=dp[1:idx+1]
            dq2=dq[1:idx+1]
        else:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i


    dq2.sort() 
    for i in range(len(dq2)-1,-1,-1):
        del a[dq2[i]]
    print(dq2)

icnt=0
while len(a)>0:
    loopa()        
    icnt+=1

print(icnt)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

icase=0
if icase==0:
    n=int(input())
    a=[0]*n
    for i in range(n):
        a[i]=int(input())

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -1
    dq = [0]*(n+1)    
    
#    print(n,a,dp)
    for i in range(n):
        idx = bisect(dp, a[i]-1)
        if dp[idx]==10**10:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i
            dp2=dp[1:idx+1]
            dq2=dq[1:idx+1]
        else:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i

#    print("i:",i,"a:",a,"dp2:",dp2) 
#    dq2.sort(reverse=True) 
    dq2.sort() 
#    print("i:",i,"dp2:",dp2,"dq2:",dq2)            
    for i in range(len(dq2)-1,-1,-1):
#        print(i,dq2[i],a[dq2[i]])
        del a[dq2[i]]
#        print("i:",i,"a:",a,"dp2:",dp2)            

icnt=0
while len(a)>0:
#    print(a)
    loopa()        
    icnt+=1
#    print(icnt)

print(icnt)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = ILs(N)

MAXS = [A[0]] + [1 for i in range(N)]
now = 0
for a in A[1:]:
  p = bisect.bisect_right(MAXS,-a)
  if p >= now:
    MAXS[now] = -a
    now += 1
  else:
    MAXS[p] = -a
print(now+1)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = ILs(N)

MAXS = [A[0]] + [1 for i in range(N)]
now = 1
for a in A[1:]:
  p = bisect.bisect_right(MAXS,-a)
  if p >= now:
    MAXS[now] = -a
    now += 1
  else:
    MAXS[p] = -a
print(now)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque
N = int(input())
A = deque([])
for i in range(N):
  A.append(int(input()))

dp = deque([])
l = len(A)
for i,a in enumerate(A):
  if len(dp)==0:
    dp.append(a)
  elif a < dp[-1]:
    dp.appendleft(a)
  elif a >= dp[-1]:
    dp.append(a)
  else:
    pos = bisect.bisect_left(dp, a)
    A.append(dp[pos])
    dp[pos] = a

print(len(dp))

Submission status: Wrong Answer

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

cnt = 0
ans = 0
for i in range(1,n):
  if a[i] <= a[i-1]:
    cnt += 1
  else:
    ans = max(ans, cnt)
    cnt = 0
ans = max(ans, cnt)
print (ans + 1)

Submission status: Wrong Answer

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

cnt = 0
ans = 0
for i in range(1,n):
  if a[i] <= a[i-1]:
    cnt += 1
  else:
    cnt = 0
    ans = max(ans, cnt)
ans = max(ans, cnt)
print (ans + 1)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[int(input()) for _ in range(n)]
ans=[a[0]]
ansl=1
from bisect import bisect_right
for ai in a[1:]:
  tmp=bisect_right(ans,ai)
  if tmp<ansl:
    ans[tmp]=ai
  else:
    ans.append(ai)
    ansl+=1
print(ansl)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline #inputに置き換え可能

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

cnt = 1
ans = 1
for i in range(n-1):
    if a[i] >= a[i+1]:
        cnt += 1
        ans = max(ans, cnt)
    else:
        cnt = 1
print(ans)

Submission status: Wrong Answer

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


S = []
for i in range(N):
    posi = bisect.bisect_right(S,A[i])
    if posi == 0:
        S.insert(0,A[i])
    else:
        S[posi-1] = A[i]

print(len(S))

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
nums = []

for i in range(N):
    num = int(input())
    if i == 0:
        nums.append(num)
    else:
        if nums[-1] < num:
            nums[-1] = num
        else:
            insert_index = bisect.bisect_left(nums, num)
            if insert_index == 0:
                nums.insert(0, num)
            else:
                nums[insert_index] = num
#     print(nums)
# print(nums)
print(len(nums))

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())

S = list(int(input()) for _ in range(N))

d = [S[0]]
cnt = 1
for i in range(1, N):
    temp = S[i]
    if d[0] >= temp:
        heapq.heappush(d, temp)
        cnt += 1
        continue
    elif d[-1] < temp:
        d[-1] = temp
        continue
    ok = 0
    ng = cnt-1
    t = (ok+ng)//2
    while ok+1 < ng:
        t = (ok+ng)//2
        if d[t] < temp:
            ok = t
        else:
            ng = t
    d[t] = temp
    heapq.heapify(d)

print(cnt)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())

S = list(int(input()) for _ in range(N))

d = [S[0]]
cnt = 1
for i in range(1, N):
    temp = S[i]
    if d[0] >= S[i]:
        heapq.heappush(d, temp)
        cnt += 1
        continue
    ok = 0
    ng = cnt-1
    t = (ok+ng)//2
    while ok+1 < ng:
        t = (ok+ng)//2
        if d[t] < temp:
            ok = t
        else:
            ng = t
    d[t] = temp
    heapq.heapify(d)

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())

S = list(int(input()) for _ in range(N))
d = set([S[0]])
ans = 1

for i in range(1, N):
    num = S[i]
    temp = 10**9+1
    for t in d:
        if t > num and t < temp:
            temp = t
    if temp == 10**9 + 1:
        ans += 1
        d.add(num)
    else:
        d.remove(temp)
        d.add(num)
print(ans)

Submission status: Wrong Answer

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

cnt = 0
for i in range(1, n):
    if a[i] <= a[i - 1]:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

m = a[0]
pre_num = a[0]
cnt = 1
for i in range(1, n):
    if pre_num < a[i]:
        pre_num = a[i]
        continue
    
    if m >= a[i]:
        cnt += 1
        m = a[i]

    pre_num = a[i]
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    seq = [int(input()) for _ in range(n)]
    seq.reverse()

    # リストseqからLISの長さを出す

    import bisect
    
    def main():

        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]
        return len(LIS)
    print(main()-1)
    




resolve()

Submission status: Wrong Answer

Solution code:
import bisect

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

def lis(S):
    from bisect import bisect_left
    L = [S[0]]

    for s in S[1:]:
        if s >= L[-1]:
            L.append(s)
        else:
            L[bisect_left(L, s)] = s
    return len(L)

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

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ans = 1
cur_min = A[0]
for i in range(1, N):
    if A[i] <= cur_min:
        ans += 1
        cur_min = A[i]

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ans = 1
cur_min = A[0]
for i in range(1, N):
    if A[i] > A[i-1]:
        continue
    else:
        if A[i] <= cur_min:
            ans += 1
            cur_min = A[i]

print(ans)

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(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:
# ABC134E

import sys
input=sys.stdin.readline


def bisect(ite,x):
    st=-1
    en=len(ite)
    while(en-st>1):
        mid=(st+en)//2
        if ite[mid]>x:
            st=mid
        else:
            en=mid
    return en

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    cnt=0
    lbds=[A[0]]
    for i in range(1,N):
        if lbds[-1]>=A[i]:
            lbds+=[A[i]]
        else:
            x=bisect(lbds,A[i])
            if lbds[x]==A[i]:
                lbds[x+1]=A[i]
            else:
                lbds[x]=A[i]
            
    print(len(lbds)+cnt)
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC134E

import sys
input=sys.stdin.readline


def bisect(ite,x):
    st=-1
    en=len(ite)
    while(en-st>1):
        mid=(st+en)//2
        if ite[mid]>x:
            st=mid
        else:
            en=mid
    return en

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    lis=[A[0]]
    for i in range(1,N):
        if lis[-1]>=A[i]:
            lis+=[A[i]]
        else:
            lis[bisect(lis,A[i])]=A[i]
            
    print(len(lis))
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC134E

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    cho={}
    cho[A[0]]=1
    maxset=set([A[0]])
    
    for i in range(1,N):
        remset=set()
        for m in maxset:
            if A[i]>m:
                remset.add(m)
            if A[i]==m:
                if cho.get(m,None) is None:
                    cho[m]=1
                else:
                    cho[m]+=1
        if len(remset)>0:
            maxset.remove(max(remset))
            maxset.add(A[i])
        else:
            maxset.add(A[i])
            
    print(max(len(maxset),max(cho.values())))
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ABC134E

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    cho=1
    maxset=set([A[0]])
    
    for i in range(1,N):
        remset=set()
        for m in maxset:
            if A[i]>m:
                remset.add(m)
            if A[i]==m:
                cho+=1
        if len(remset)>0:
            maxset.remove(max(remset))
            maxset.add(A[i])
        else:
            maxset.add(A[i])
            
    print(maxset)
    print(max(len(maxset),cho))
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from bisect import bisect_left
lis = [1]
for a in As:
    if a>=lis[-1]:
        lis.append(a)
    else:
        lis[bisect_left(lis, a)-1] = a

print(len(lis))

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

from bisect import bisect_left
lis = [1]
for a in As:
    if a>=lis[-1]:
        lis.append(a)
    else:
        lis[bisect_left(lis, a)] = a

print(len(lis))

Submission status: Wrong Answer

Solution code:
n=int(input())
m=[]
m.append(int(input()))
count=1
for i in range(n-1):
  k=int(input())
  if k<=m[-1]:
    m.append(k)
    count+=1
  else:
    r=count-1
    l=0
    while l+1<r:
      try1=(r+l)//2
      if m[try1]>k:
        l=try1
      else:
        r=try1
    if m[l]>k:
      m[r]=k
    else:
      m[l]=k
print(count)

Submission status: Wrong Answer

Solution code:
def bisect_right_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番右側のidx+1となる。
    '''
    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

def main():
  N = int(input())
  ans = 1
  lis_min = [int(input())]
  for i in range(N-1):
    a = int(input())
    index = bisect_right_reverse(lis_min, a)
    if index != len(lis_min):
      lis_min[index-1] = a
    else:
      ans += 1
      lis_min.append(a)
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import bisect
# from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt
 
n = int(input())
li = [int(input()) for i in range(n)]
li = [-x for x in li]

X = []
X.append(li[0])

for i in range(1,n):
    idx = bisect.bisect_right(X,li[i])
    if idx==len(X):
        X.append(li[i])
    else:
        X[idx-1] = li[i]

print(len(X))

Submission status: Wrong Answer

Solution code:
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

n = int(input())
li = [int(input()) for i in range(n)]

tmp = [li[0]]
minli = li[0]

for i in range(1,n):
    if li[i] <= minli:
        minli = li[i]
        tmp.append(li[i])
    else:
        idx = bisect_left_reverse(tmp,li[i])
        tmp.insert(idx,li[i]) 
        tmp.pop(idx-1)

print(len(tmp))

Submission status: Wrong Answer

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

tmp = [li[0]]
minli = li[0]

for i in range(1,n):
    if li[i] <= minli:
        minli = li[i]
        tmp.append(li[i])
    else:
        for cnt, j in enumerate(tmp):
            if li[i] > j:
                tmp[cnt] = li[i]
                break

print(len(tmp))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())

    vec = [INF] * N
    for a in reversed(A[:-1]):
        vec[bisect_right(vec, a)] = a

    print(N - vec.count(INF))
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    def append_return(dict,x,y):
        if x in dict:
            dict[x].append(y)
        else:
            dict[x] = [y]

        return dict

    colori_max_map = {}
    max_colori_map = {}
    maxs = []
    ans = 0
    for i in range(N):
        a = A[i]
        opt_i = bisect.bisect_left(maxs,a)

        minim_l = []
        for di in [-1,0,1]:
            j = opt_i + di
            if 0<=j<len(maxs) and a > maxs[j]:
                minim_l.append((a-maxs[j],j))

        # print(a,minim_l,maxs,opt_i)
        color_i = 0
        if len(minim_l) > 0:
            minim_l.sort()
            color_i = minim_l[0][1]
            maxs.remove(colori_max_map[color_i])
            max_colori_map[colori_max_map[color_i]].remove(color_i)
        else:
            color_i = ans
            ans += 1

        # print("ans",ans)
        colori_max_map[color_i] = a
        max_colori_map = append_return(max_colori_map,a,color_i)
        bisect.insort_left(maxs,a)

    # print(max_colori_map)
    # print(colori_max_map)
    print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    def append_return(dict,x,y):
        if x in dict:
            dict[x].append(y)
        else:
            dict[x] = [y]

        return dict

    colori_max_map = {}
    max_colori_map = {}
    maxs = []
    ans = 0
    for i in range(N):
        a = A[i]
        opt_i = bisect.bisect_left(maxs,a)

        # print(opt_i)
        minim_l = []
        for di in [-1,0,1]:
            j = opt_i + di
            if 0<=j<len(maxs) and a > maxs[j]:
                minim_l.append((a-maxs[j],j))

        color_i = 0
        # print(minim_l)
        if len(minim_l) > 0:
            minim_l.sort()
            color_i = minim_l[0][1]
            # print("already",i,color_i)
            maxs.remove(colori_max_map[color_i])
            max_colori_map[colori_max_map[color_i]].remove(color_i)
        else:
            color_i = ans
            ans += 1

        colori_max_map[color_i] = a
        max_colori_map = append_return(max_colori_map,a,color_i)
        maxs.append(a)

    # print(max_colori_map)
    # print(colori_max_map)
    print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import sys
import bisect

input = lambda: sys.stdin.readline().rstrip()

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


def solve():

    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]

    ans = len(LIS)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc134/tasks/abc134_e　

from bisect import bisect_left

N = int(input())

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

LIS = [A[0]]
cnt = 0

for a in A:
    if a > LIS[-1]:
        LIS.append(a)
    else:
        ind = bisect_left(LIS, a)
        LIS[ind] = a
        if ind == 0:
            cnt += 1

print(cnt)

Submission status: Wrong Answer

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

import bisect
#a=[0,2,3,4,67,8]
#a.sort()
#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

color=[1]
lencolor=1
for aa in a:
    aa=-1*aa
    i=bisect.bisect_left(color, aa)
    if i==lencolor:
        color.append(aa)
        lencolor+=1
        #print("insert")
    else:
        color[i]=aa
        #print("update")
    #print(color,aa) 
print(lencolor)

Submission status: Wrong Answer

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

import bisect
#a=[0,2,3,4,67,8]
#a.sort()
#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

color=[-1]

for aa in a:
    i=bisect.bisect_left(color, aa)
    if i==0:
        color.insert(aa,0)
    else:
        color[i-1]=aa
        
print(len(color))

Submission status: Wrong Answer

Solution code:
N = int(input())
C = {}
for i in range(N):
    k = input()
    if C.get(k, -1) == -1:
        C[k] = [i]
    else:
        C[k].append(i)
C = sorted(C.items(), key=lambda x:x[0])

before = 10**6
ans = 0
for i in range(len(C)):
    j = 0
    while(True):
        now = C[i][1][j]
        if now < before:
            ans += 1
            for k in range(j+1,len(C[i][1])):
                if C[i][1][k] < before:
                    ans += 1
            before = now
            break
        j += 1
        if j == len(C[i][1]):
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
ans = 0
X = [int(input())for _ in range(N)]
A = []
for a in X[::-1]:
    if len(A) == 0:
        A.append(a)
    elif A[-1] <= a:
        A.append(a)
    else:
        i = bisect.bisect_left(A, a)
        A[i] = a

print(len(A))

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
now = - float('inf')
for _ in range(N):
    a = int(input())
    if a <= now:
        ans += 1
    now = a

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ans = 0
now = - float('inf')
for _ in range(N):
    a = int(input())
    if a < now:
        ans += 1
    now = a

print(ans)