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:
def p_e():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    ans = [-1]

    for a in A:
        is_set = False
        for l in ans:
            if l < a:
                l = a
                is_set = True
                break

        if not is_set:
            ans.append(a)

    print(len(ans))


if __name__ == '__main__':
    p_e()

Submission status: Wrong Answer

Solution code:
def abc_134e(N, A):
    minval = []
    reverse = list(reversed(A))

    for val in reverse:
        can_append = True
        for j, arr in enumerate(minval):
            if arr > val:
                minval[j] = val
                can_append = False
                break

        if can_append:
            minval.append(val)

    print(len(minval))


if __name__ == "__main__":
    N = int(input())
    A = []
    for i in range(N):
        A.append(str(input()))
    abc_134e(N, A)

Submission status: Wrong Answer

Solution code:
n=int(input())

a=[0 for i in range(n)]
minute=[a[n-1]]
count=1
for i in range(n):
    a[i]=int(input())

for i in range(n-1):
    index = n - i - 2
    x=[]
    y=False
    for j in range(len(minute)):
        if a[index]<minute[j]:
            x.append(minute[j])
            y=True
    if y:
        minute[minute.index(min(x))] = a[index]
    else:
        count+=1
        minute.append(a[index])



print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())

a=[0 for i in range(n)]
minute=[a[n-1]]
count=1
for i in range(n):
    a[i]=int(input())

for i in range(n-1):
    index = n - i - 2
    x=False
    for m in minute:
        if a[index]<m:
            x=True

    if not x:
        count+=1
        minute.append(a[index])



print(count)

Submission status: Wrong Answer

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

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

print(len(color))

Submission status: Wrong Answer

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

color = [a[0]]
for i in range(1,n):
    idx = bisect_left(color,a[i])
    if idx == 0:
        color.insert(idx,a[i])
    elif idx == len(color):
        color[-1] = a[i]
    elif color[idx] == a[i]:
        color[idx - 1] = a[i] 
    elif color[idx] != a[i]:
        color[idx] = a[i] 

print(len(color))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
color = 0
a_min_pre = a[-1]
a_min = a[-1]
for i in a:
    if a_min <= i:
        color += 1
        if i < a_min_pre:
            color -= 1
        a_min_pre = a_min
        a_min = i

print(color)

Submission status: Wrong Answer

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

color = 0
a_max = a[-1]
for i in a:
    if i >= a_max:
        color += 1
        a_max = i

print(color)

Submission status: Wrong Answer

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

s_min = a[0]
colors = 1
  
for i in range(1,n):
  if a[i] <= s_min:
    colors = colors + 1
    s_min = a[i]

print(colors)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N = int(input())
A = []
for i in range(N):
    A.append(-int(input()))
D = [A[0]]
num = 0
for i in range(1, len(A)):
    if A[i] >= D[-1]:
        D.append(A[i])
    else:
        D[bisect_left(D, A[i])] = A[i]

print(len(D))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

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

b = []

ans = 1
b.append(a[n-1])

for i in range(n-2, -1, -1):
    if a[i] >= b[-1]:
        b.append(a[i])
    else:
        x = bisect_right(b,a[i])
        b[x] = a[i]
        x -= 1
        while x >= 0:
            if b[x] > b[x+1]:
                b[x],b[x+1] = b[x+1],b[x]
                x -= 1
            else:
                break
    print(b)

print(len(b))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as BL

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

b = []

ans = 1
b.append(a[n-1])

for i in range(n-2, -1, -1):
    if a[i] >= b[-1]:
        b.append(a[i])
    else:
        x = BL(b,a[i])
        b[x] = a[i]
        x -= 1
        while x >= 0:
            if b[x] > b[x+1]:
                b[x],b[x+1] = b[x+1],b[x]
                x -= 1
            else:
                break

print(len(b))

Submission status: Wrong Answer

Solution code:
#E問題
import bisect

N = int(input())
A = [int(input()) for i in range(N)]
B = []
for i in range(N):
    if len(B) == 0:
        B.append(A[i])
    else:
        if B[0] >= A[i]:
            B.append(A[i])
        else:
            index = bisect.bisect_left(B,A[i])-1
            B[index] = A[i]
    B.sort()
print(len(B)+1)

Submission status: Wrong Answer

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

ans = 1
m = 0
for i in range(N-1):
    if a[i] < a[i+1]:
        continue
    else:
        ans += 1
        if a[m] < a[i+1]:
            ans -= 1
        m = i+1

print(ans)

Submission status: Wrong Answer

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

dp = []
for a in A:
    i = bisect.bisect_right(dp, a)
    if i >= len(dp):
        dp.append(a)
    else:
        dp[i] = a

print(N-len(dp))

Submission status: Wrong Answer

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

dp = []
for a in A:
    i = bisect.bisect_right(dp, a)
    if i >= len(dp):
        dp.append(a)
    else:
        dp[i] = a

print(N-len(dp))

Submission status: Wrong Answer

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

dp = []
for a in A:
    i = bisect.bisect_right(dp, a)
    if i >= len(dp):
        dp.append(a)
    else:
        dp[i] = a

print(N-len(dp))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for count in range(N)]
color = 0
while len(A) > 0:
    color += 1
    check = 0
    i = 0
    while i < len(A):
        if A[check] < A[i]:
            del A[check]
            check = i - 1
            i -= 1
        i += 1
    del A[check]
    print(A)
print(color)

Submission status: Wrong Answer

Solution code:
import bisect

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

c.append(a[0])

for i in range(1,n):
  j=bisect.bisect_right(c,a[i])
  if c[j-1]<a[i]:
    c[j-1]=a[i]
  else:
    c.insert(j,a[i])
print(len(c))

Submission status: Wrong Answer

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

for i in range(1, N):

    index = bisect.bisect_right(now, -A[i])
    if index == len(now):
        now.append(-A[i])
    else:
        now[index] = A[i]
print(len(now))

Submission status: Wrong Answer

Solution code:
import bisect

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

LIS = [a[-1]]
for i in range(n - 2, -1, -1):
    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:
import bisect
n = int(input())
a = []
for i in range(n):
    temp = int(input())
    a.append(temp)
a.reverse()
b = [a[0]]
counter = 1
for i in range(1,n):
    if a[i] >= b[-1]:
        counter += 1
        b.append(a[i])
    else:
        ind = bisect.bisect_left(b,a[i])
        b[ind] = a[i]
print(counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
    temp = int(input())
    a.append(temp)
a.reverse()
counter = 0
mxm = 0
for i in range(n):
    if mxm <= a[i]:
        counter += 1
        mxm = a[i]
print(counter)

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect

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

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

for a in A[1:]:
  if a <= ans[0]:
    ans.appendleft(a)
  elif a > ans[-1]:
    ans[-1] = a
  else:
    i = bisect.bisect_left(ans, a)
    ans[i] = a

print(len(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
a = a[::-1]
cnt = 0
while len(a) != 0:
    maxVal = max(a)
    maxIndex = a.index(maxVal)
    a.pop(maxIndex)
    cnt += 1
    i = len(a) - 1
    while i >= 0:
        if i >= maxIndex and a[i] < maxVal:
            a.pop(i)
        i -= 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N               =   int(input())
color_list      =   []
color_number    =    -1
flag            =   1
for i in range(N):
    A   =   int(input())
    if(color_number == -1):
        color_list.append(A)
        color_number    +=  1
    else:
        for j in range(len(color_list)):
            if(color_list[j] < A):
                color_list[j]    =  A
                flag             =  0
                break
        if(flag):    
            color_number    +=  1
            color_list.append(A)

print(len(color_list))

Submission status: Wrong Answer

Solution code:
N               =   int(input())
color_list      =   []
color_number    =    -1

for i in range(N):
    A   =   int(input())
    if(color_number == -1):
        color_list.append(A)
        color_number    +=  1
    else:
        if(color_list[color_number] < A):
            color_list[color_number]    =   A
        else:
            color_number    +=  1
            color_list.append(A)

print(len(color_list))

Submission status: Wrong Answer

Solution code:
N = int(input())
a = int(input())
l = [a]
d = {a: 1}
ans = 1
for _ in range(1, N):
    a = int(input())
    if a in d:
        d[a] += 1
        ans += 1
    else:
        v = l[0]
        if v < a:
            if d[v] == 1:
                del d[v]
                l[0] = a
            else:
                d[v] -= 1
                l.insert(0, a)
        elif l[-1] > a:
            l.append(a)
            ans += 1
        else:
            left, right = 0, len(l) - 1
            while left + 1 != right:
                i = (left + right) // 2
                x = l[i]
                if x > a:
                    left = i
                else:
                    right = i
            v = l[right]
            if d[v] == 1:
                del d[v]
                l[right] = a
            else:
                d[v] -= 1
                l.insert(right, a)
        d[a] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = int(input())
l = [a]
d = {a: 1}
ans = 1
for _ in range(1, N):
    a = int(input())
    if a in d:
        d[a] += 1
        ans += 1
    else:
        v = l[0]
        if v < a:
            if d[v] == 1:
                del d[v]
                l[0] = a
            else:
                d[v] -= 1
                l.insert(0, a)
            d[a] = 1
        elif l[-1] > a:
            l.append(a)
            d[a] = 1
            ans += 1
        else:
            left, right = 0, len(l)
            while left + 1 != right:
                i = (left + right) // 2
                x = l[i]
                if x > a:
                    left = i
                else:
                    right = i
            v = l[right]
            if d[v] == 1:
                del d[v]
                l[right] = a
            else:
                d[v] -= 1
                l.insert(right, a)
            d[a] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
c = {A[0]}
d = {A[0]: 1}
ans = 1
for a in A[1:]:
    if a in c:
        d[a] += 1
        ans += 1
    else:
        l = list(c)[::-1]
        v = l[0]
        if v < a:
            if d[v] == 1:
                c.remove(v)
            else:
                d[v] -= 1
            d[a] = 1
            c.add(a)
        elif l[-1] > a:
            c.add(a)
            d[a] = 1
            ans += 1
        else:
            left, right = 0, len(l)
            while left + 1 != right:
                i = (left + right) // 2
                x = l[i]
                if x > a:
                    left = i
                else:
                    right = i
            v = l[right]
            if d[v] == 1:
                c.remove(v)
            else:
                d[v] -= 1
            d[a] = 1
            c.add(a)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
input = sys.stdin.readline
n = int(input().strip())
q = [-int(input().strip())]
qapp = q.append
bis_l = bisect.bisect_left
for i in range(n-1):
  a = -int(input().strip())
  if q[-1] <= a:
    qapp(a)
  else:
    b = bis_l(q,a)
    q[b] = a
print(len(q))

Submission status: Wrong Answer

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

count = 0
while data != []:
    count += 1
    mot = data[0]
    next = []
    for i in range(1,len(data)):
        if not mot < data[i]:
            next.append(data[i])
    data = next

print(count)

Submission status: Wrong Answer

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

index = n-1
flag = True
count = 0
while flag:
    if index == 0:
        count += 1
        break
    flag = False
    count += 1
    for i in range(index-1,-1,-1):
        if data[index] >= data[i]:
            index = i
            flag = True
            break

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
table = []
for i in range(N):
    n = int(input())
    min_dif = n
    min_table_index = -1
    for index, t in enumerate(table):
        if t[-1] >= n:
            continue
        else:
            dif = n - t[-1]
            if dif < min_dif:
                min_dif = dif
                min_table_index = index
    if min_table_index == -1 :
        table.append([n])
    else:
        table[min_table_index].append(n)
print(len(table))

Submission status: Wrong Answer

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

    for j in range(len(ans)):
        if ans[j][-1]<i:
            ans[j]+=[i]
            break
        else:
            if j==len(ans)-1:
                ans+=[[i]]
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    if len(li) == 0:
        break
    ans += 1
    max_index = li.index(max(li))
    li = li[max_index+1:]

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
li = np.array([int(input()) for _ in range(n)])
#li = np.flip(li, axis = 0)
ans = 0
for i in range(n):
    if len(li) == 0:
        break
    ans += 1
    max_index = li.argmax()
    li = li[max_index+1:]
    print(li)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
li = np.array([int(input()) for _ in range(n)])
#li = np.flip(li, axis = 0)
ans = 0
while 1:
    if len(li) == 0:
        break
    ans += 1
    max_index = li.argmax()
    li = li[max_index+1:]
    
print(ans)

Submission status: Wrong Answer

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

ans = 0
li_copy = li.copy()
while 1:
    if len(li) == 0:
        break
    ans += 1
    back = li[-1]
    li = [j for j in li if j >= back]
    li = li[:-1] 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import collections


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


def main():
    n = int(input())
    la = [int(input()) for _ in range(n)]
    result = collections.deque()
    for a in la:
        idx = bisect.bisect_left(result, a)
        if idx == 0:
            result.appendleft(a)
        else:
            result[idx - 1] = a
    print(len(result))
    print(result)


main()

Submission status: Wrong Answer

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

temp_result = 1
result = 1

for i in range(1, len(A)):
  if A[i-1] >= A[i]:
    temp_result += 1
  else:
    result = max(temp_result, result)
    temp_result = 1

print(max(temp_result, result))

Submission status: Wrong Answer

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

temp_result = 1
result = 1

for i in range(1, len(A)):
  if A[i-1] >= A[i]:
    temp_result += 1
  else:
    result = max(temp_result, result)
    temp_result = 1

print(max(temp_result, result))

Submission status: Wrong Answer

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

temp_result = 1
result = 1

for i in range(1, len(A)):
  if A[i-1] >= A[i]:
    temp_result += 1
  else:
    result = max(temp_result, result)
    temp_result = 1

if temp_result > result:
  result = temp_result

print(result)

Submission status: Wrong Answer

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

temp_result = 1
result = 1

for i in range(1, N):
  if A[i-1] >= A[i]:
    temp_result += 1
  elif temp_result > result:
    result = temp_result
    temp_result = 1

if temp_result > result:
  result = temp_result

print(result)

Submission status: Wrong Answer

Solution code:
import bisect

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
def bs(A, t):
  l, r = 0, len(A) - 1

  while l < r:
    mid = (l + r) // 2
    if t <= A[mid]:
      r = mid - 1
    else:
      l = mid + 1
  else:
    return l


N = int(input().strip())
A = [0] * N

# reverse
for i in range(N):
  A[- i - 1] = int(input().strip())

B = [A[0]]
for i in range(1, N):
  a = A[i]

  if a < B[0]:
    B[0] = a
  elif a >= B[-1]:
    B.append(a)
  else:
    l = bs(B, a)
    B[l] = a

print(len(B))

Submission status: Wrong Answer

Solution code:
N = int(input().strip())
B = [int(input().strip())]
min_value = B[0]
for _ in range(N - 1):
  a = int(input().strip())
  if a <= min_value:
    min_value = a
    B.append(a)
  else:
    B = sorted(B)
    for i in range(len(B)):
      if a > B[i]:
        B[i - 1] = a

print(len(B))

Submission status: Wrong Answer

Solution code:
#数列Aが与えられたとき、順番を変えずに小さい順の数列に分割する。このときの分割の最小を求める
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
counter = 1
small = A[0]
for i in range(N - 1):
    i += 1
    if A[i] <= small:
        small = A[i]
        counter += 1
print(counter)

Submission status: Wrong Answer

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

import sys
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

def LIS(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a >= L[-1]:
            # Lの末尾よりaが大きければ増加部分列を延長できる(今回は広義(=を含む))
            L.append(a)
        else:
            # そうでなければ、「aより小さい最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_left(L, a)] = a
    return len(L)

# 後ろからLIS
print(LIS(A[::-1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
cnt=0
while len(a)>0:
  print(a)
  cnt+=1
  if a.index(max(a))==0:
    del a[0]
  else:
    for i in range(a.index(max(a)),a.index(min(a[:a.index(max(a))]))-1,-1):
      del a[i]
print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int, input())) for _ in range(n)]
c = [a[0]]
c_len = len(c)

for i in range(1, n):
    for j in range(c_len):
        if c[j] < a[i]:
            c[j] = a[i]
            break
    else:
        c.append(a[i])
        c_len += 1
        continue
    c.sort(reverse=True)
print(c_len)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int, input())) for _ in range(n)]
c = [a[0]]
c_len = len(c)

for i in range(1, n):
    for j in range(len(c)):
        if c[j] < a[i]:
            c[j] = a[i]
            break
    else:
        c.append(a[i])
        c_len += 1
    c.sort(reverse=True)
print(c_len)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = []

for _ in range(N):
    A.append(int(input()))

colored = [False] * N
goal = [True] * N

color_num = 0

while colored != goal:
    start = colored.index(False)
    base = A[start]
    colored[start] = True

    print("check from {}".format(start))

    for i in range(start+1, N):
        if colored[i] == False:
            if base < A[i] :
                colored[i] = True
                base = A[i]

    color_num += 1

print(color_num)

Submission status: Wrong Answer

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

first = A[0]
ans = 0
for num in A:
    if num <= first:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

b = 10000000000
ans = 0
for i in a:
    if i < b:
        ans += 1
        b = i
    elif i == b:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

b = 1000000000
ans = 0
for i in a:
    if i < b:
        ans += 1
        b = i
    elif i == b:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

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

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

# それぞれの色の最大値を入れる筒のリスト
t = []

for i in a:
    # それぞれの色のどの値よりも小さかったとき
    # 筒よりも小さかったとき
    if len(t) == 0:
        t.append(i)
        continue
    if len(t) > 0 and i <= t[0]:
        t.insert(0, i)
    # 筒よりも大きかったとき
    idx = bisect.bisect_left(t, i)
    t[idx-1] = i
    # print(t)

print(len(t))

Submission status: Wrong Answer

Solution code:
"""
提出 #6475942 を参考に作成
"""

import bisect


def solve():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color_list = [A[-1]]
    for a in reversed(A[:-1]):
        # a より大きい数の中で一番小さい数の場所を取得する
        c = bisect.bisect_left(color_list, a + 1)  
        print(c)
        if c == len(color_list):
            color_list.append(a)
        else:
            color_list[c] = a
    print(len(color_list))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
update_list=[11 for _ in range(n+1)]
for old_element in range(n):
    update_position=bisect(update_list,-a[old_element])
    update_list[update_position]=-a[old_element]

counter=0
for sign in update_list:
    if sign<0:
        counter+=1
print(counter)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
update_list=[11 for _ in range(n+1)]
for old_element in range(n):
    update_position=bisect(update_list,-a[old_element])
    update_list[update_position]=-a[old_element]

counter=1
for sign in update_list:
    if sign>0:
        counter+=1
print(counter)

Submission status: Wrong Answer

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

for i in range(N):
    temp =  int(input())
    ind = bisect.bisect_right(nums, temp)
    if ind == 0:
        nums.appendleft(temp)
    # else:
        # print(ind)
print(len(nums))

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
nums = []
for i in range(N):
    temp = int(input())
    ind = bisect.bisect_left(nums, temp)
    if ind == 0:
        nums = [temp] + nums

print(len(nums))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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


B = []
Bc = A[-1]
B.append(Bc)
cnt = 0

for i in range(N-2, -1, -1):
    if A[i]<Bc:
        Bc = A[i]
    else:
        if A[i]>=max(B):
            B.append(A[i])
            B.sort()
            Bc = A[i]
        else:
            index = bisect_left(B, A[i])
            B[index] = A[i]
            Bc = A[i]

print(len(B))

Submission status: Wrong Answer

Solution code:

import bisect

n = int(input())
num_list = []
for i in range(n):
    num_list.append(int(input()) * -1) 

dp = [1] * n 

for i in num_list:
    indx = bisect.bisect_left(dp, i)
    dp[indx] = min(dp[indx], i)

ans = sum(x < 1 for x in dp)

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N = int(input())
A = list(int(input()) for _ in range(N))
INF = 10 ** 9 + 1

dp = [INF]
for i, a in enumerate(A):
    if -a >= dp[-1]:
        dp.append(-a)
    else:
        j = bisect_left(dp, -a)
        dp[j] = -a

print(len(dp))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys, math, bisect, random, itertools
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print(n*n*3)
    return

#B
def B():
    n, d = LI()
    print((n-1)//(2*d+1)+1)
    return

#C
def C():
    n = II()
    a = IR(n)
    b = a[::1]
    b.sort()
    for i in range(n):
        if a[i] == b[-1]:
            print(b[-2])
        else:
            print(b[-1])
    return

#D
def D():
    n = II()
    a = [0] + LI()
    for i in range(n // 2, 0, -1):
        x = sum(a[i::i])
        if x % 2 != a[i]:
            a[i] ^= 1
    ans = []
    x = 0
    for i in range(1, n + 1):
        if a[i]:
            ans.append(str(i))
            x += 1
    print(x)
    if x == 0:
        return
    print(" ".join(ans))
    return

#E
def E():
    n = II()
    a = IR(n)
    dp = deque([a[0]])
    ans = 1
    for i in a[1:]:
        x = bisect_right(dp, i)
        y = bisect_left(dp, i)
        if y == 0:
            ans += 1
            dp.appendleft(i)
        else:
            if x == y:
                dp[y - 1] = i
            else:
                if x >= ans:
                    ans += 1
                    dp.append(i)
                else:
                    dp[y - 1] = i
    print(ans)
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys, math, bisect, random, itertools
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print(n*n*3)
    return

#B
def B():
    n, d = LI()
    print((n-1)//(2*d+1)+1)
    return

#C
def C():
    n = II()
    a = IR(n)
    b = a[::1]
    b.sort()
    for i in range(n):
        if a[i] == b[-1]:
            print(b[-2])
        else:
            print(b[-1])
    return

#D
def D():
    n = II()
    a = [0] + LI()
    for i in range(n // 2, 0, -1):
        x = sum(a[i::i])
        if x % 2 != a[i]:
            a[i] ^= 1
    ans = []
    x = 0
    for i in range(1, n + 1):
        if a[i]:
            ans.append(str(i))
            x += 1
    print(x)
    if x == 0:
        return
    print(" ".join(ans))
    return

#E
def E():
    n = II()
    a = IR(n)
    dp = deque([a[0]])
    ans = 1
    for i in a[1:]:
        x = bisect_right(dp, i)
        if x == 0:
            ans += 1
            dp.appendleft(i)
        else:
            if dp[x - 1] != i:
                dp[x - 1] = i
            else:
                if x >= ans:
                    ans += 1
                    dp.append(i)
                else:
                    x = bisect_left(dp, i)
                    if x == 0:
                        ans += 1
                        dp.appendleft(i)
                    else:
                        dp[x - 1] = i
            
    print(ans)
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()