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:
#!/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 = [a[0]]
    ans = 1
    for num, i in enumerate(a[1:]):
        x = bisect_right(dp, i)
        if x == 0:
            ans += 1
            dp.append(i)
        else:
            if x >= ans:
                if dp[x - 1] != i:
                    dp[x - 1] = i
                else:
                    ans += 1
                    dp.append(i)
            else: 
                dp[x - 1] = i
        dp.sort()
    print(ans)
    return

#F
def F():
    return

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left, bisect_right

N=input()
seq=[ int(sys.stdin.readline().strip())*-1  for _ in range(N) ]

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

print(len(LIS))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left, bisect_right

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

LDS=[]
for i,x in enumerate(A):
	if i==0:
		LDS.append(x*-1)
	elif LDS[-1]<=x*-1:
		LDS.append(x*-1)
	else:
		p=bisect_left(LDS,x*-1)
		LDS[p]=x*-1

print len(LDS)

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)
    par = [i for i in range(n)]
    def root(n):
        if n == par[n]:
            return n
        par[n] = root(par[n])
        return par[n]
    def unite(a, b):
        a = root(a)
        b = root(b)
        if a == b:
            return True
        par[b] = a
        return True
    res = [i for i in range(n)]
    while 1:
        res1 = []
        res2 = []
        for i in range(len(a)-1):
            x = a[i]
            y = a[i + 1]
            if x < y:
                unite(res[i], res[i + 1])
            else:
                if res[i] == par[res[i]]:
                    res2.append(x)
                    res1.append(res[i])
                else:
                    res2.append(y)
                    res1.append(res[i+1])
        res = res1[::1]
        a = res2[::1]
        if res == []:
            break
    print(len(set(par)))
    return

#F
def F():
    return

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

Submission status: Wrong Answer

Solution code:
N = int(input())
nums  = [int(input()) for _  in range(N)]
cnt = 1
def division(nums):
  global cnt
  cnt += 1
  rest_nums = []
  N = len(nums)
  i = 0
  while i<N-1:
    if nums[i] >= nums[i+1]:
      rem = nums.pop(i+1)
      rest_nums.append(rem)
      N -= 1
    else:
      i +=1
  if (rest_nums != sorted(rest_nums)) or (rest_nums != list(set(rest_nums))):
    division(rest_nums)

division(nums)

print(cnt)

Submission status: Wrong Answer

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

right_list = [A[0]]
if(N == 1):
    print(1)
else:
    for i in range(1, N):
        if(A[i] > right_list[0]):
            if(A[i] > right_list[-1]):
                right_list[-1] = A[i]
            else:
                for j in range(len(right_list)):
                    if(A[i] < right_list[j]):
                        right_list[j-1] = A[i]
        else:
            right_list = [A[i]] + right_list
            

print(len(right_list))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left, bisect_right

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

LIS=[]
for i,x in enumerate(A[::-1]):
	if i==0:
		LIS.append(x)
	elif LIS[-1]<=x:
		LIS.append(x)
	else:
		p=bisect_left(LIS,x)
		LIS[p]=x

print len(LIS)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = []
MIN = 10**9 + 1
for i in range(N):
    A = int(input())
    if A <= MIN:
        X.append(A)
        MIN = A
    else:
        for j in range(len(X)):
            if X[j] < A:
                X[j] = A
                break

print(len(X))

Submission status: Wrong Answer

Solution code:
import heapq

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

for a in A[::-1][1:]:
    if B[-1] > a:
        B.pop(-1)
    heapq.heappush(B, a)

print(len(B))

Submission status: Wrong Answer

Solution code:
import heapq

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

for a in A[::-1][1:]:
    if B[-1] >= a:
        B.pop(-1)
    heapq.heappush(B, a)

print(len(B))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left, bisect_right

N=input()
A=[]
for _ in range(N):
	a=int(sys.stdin.readline().strip())
	A.append(a*-1)

LIS=[]

for i,x in enumerate(A):
	if i==0:
		LIS.append(x)
	elif LIS[-1]<=x:
		LIS.append(x)
	else:
		p=bisect_left(LIS,x)
		LIS[p]=x

print len(LIS)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque
n = int(input())
a = [int(input()) for _ in range(n)]
tree = deque([]) 
tree.append(a[0])

for a in a[1:]:
  index = bisect.bisect_left(tree, a)
  if index == 0:
    tree.append(a)
  else:
    tree[index-1] = a
print(len(tree))

Submission status: Wrong Answer

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

for v in arr:
  check = 0
  for i, k in enumerate(max_v):
    if v < k:
      max_v[i] = k
      check = 1
      break
  if check == 0:
    max_v.append(v)
print(len(max_v))

Submission status: Wrong Answer

Solution code:
import sys
N=input()
A=[  int(sys.stdin.readline().strip()) for _ in range(N) ]

t=float("inf")

ans=0
for x in A:
	if x<=t:
		ans+=1
		t=x

print ans

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_right

def main():
    input = sys.stdin.readline
    N = int(input())
    q = deque()
    min_ = 10**9 + 1
    max_ = 0
    ans = 0
    for _ in range(N):
        n = int(input())
        if n <= min_:
            q.appendleft(n)
            min_ = n
            ans += 1
            continue

        if n > max_:
            q[-1] = n
            max_ = n
            continue

        pos = bisect_right(q, n)
        q[pos-1] = n
        min_ = q[0]

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
n = int(input())
num_list = []
for i in range(n):
    num_list.append(int(input()))
# 広義単調減少部分列の最長を求める
dp = [ [0, (10**9) + 1, (10**9) + 1] for i in range(n+1)] #[length, top_num, second_num]

for i in range(n):
    if dp[i][1] >= num_list[i]:
        dp[i+1][0] = dp[i][0] + 1
        dp[i+1][2] = dp[i][1]
        dp[i+1][1] = num_list[i]
    else:
        if dp[i][2] >= num_list[i]:
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = num_list[i]
            dp[i+1][2] = dp[i][2]
        else:
            dp[i+1][0] = dp[i][0]
            dp[i+1][1] = dp[i][1]
            dp[i+1][2] = dp[i][2]

print(dp[n][0])

Submission status: Wrong Answer

Solution code:
import collections
import bisect

n=int(input())
arr=[int(input()) for _ in range(n)][::-1]
num=1
ans=collections.deque([arr[0]])
for i in range(1,n):
  tmp=ans.popleft()
  if arr[i]<=tmp:
    ans.appendleft(tmp)
    ans.appendleft(arr[i])
  else:
    ans.appendleft(tmp)
    pos=bisect.bisect_right(ans,arr[i])
    ans[pos-1]=arr[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline

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

maxims = [A[0]]
ans = 1
minim = A[0]
for a in A[1:]:
    if a < minim:
        midx = bisect.bisect_left(maxims,a)
        m = maxims[midx]
        if m == minim:
            minim = a
        maxims[midx] = a

    else:
        maxims.append(a)
        ans += 1
        minim = a
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import bisect

n=int(input())
arr=[int(input()) for _ in range(n)]
ans=collections.deque([arr[0]])
for i in range(1,n):
  tmp=ans.popleft()
  if arr[i]<=tmp:
    ans.appendleft(tmp)
    ans.appendleft(arr[i])
  else:
    ans.appendleft(tmp)
    pos=bisect.bisect_right(ans,arr[i])
    ans[pos-1]=arr[i]
print(len(ans))

Submission status: Wrong Answer

Solution code:
import collections
import bisect

n=int(input())
arr=[int(input()) for _ in range(n)]
num=1
ans=collections.deque([arr[0]])
for i in range(1,n):
  tmp=ans.popleft()
  if arr[i]<=tmp:
    ans.appendleft(tmp)
    ans.appendleft(arr[i])
  else:
    ans.appendleft(tmp)
    pos=bisect.bisect_right(ans,arr[i])
    ans[pos-1]=arr[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
input = sys.stdin.readline

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

maxims = [A[0]]
ans = 1
minim = A[0]
for a in A[1:]:
    if a > minim:
        midx = bisect.bisect_left(maxims,a)-1
        m = maxims[midx]
        if m == minim:
            minim = a
        maxims[midx] = a

    else:
        maxims=[a]+maxims
        ans += 1
        minim = a
print(ans)

Submission status: Wrong Answer

Solution code:
# 広義最長部分増加数列の長さを求めるdef
# 配列LIS自体は広義最長部分増加文字列ではない
import bisect
def 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]
    return(len(LIS))

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

b = a[::-1]
print(lis(b))

Submission status: Wrong Answer

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

D = [[]]
for a, b in zip(A, A[1:]):
    if a >= b:
        D[-1].append((a, b))
    elif D[-1] != []:
        D.append([])

ncolor = len(D[0]) + 1  # at least
for i in range(1, len(D)):
    j = 0
    for a, _ in D[i - 1]:
        if j < len(D[i]) and a < D[i][j][1]:
            j += 1
    ncolor += len(D[i]) - j

print(ncolor)

Submission status: Wrong Answer

Solution code:
import bisect

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

def LIS(A):
    """
    returns Longest Increasing Subsequence of list A.
    """
    B = [A[0]]
    for i in range(N-1):
        if A[i+1] >= B[-1]:
            B.append(A[i+1])
        else:
            index = bisect.bisect_left(B, A[i+1])
            B[index] = A[i+1]
    return B

def LDS(A):
    """
    returns Longest Decreasing Subsequence of list A.
    """
    A = A[::-1]
    B = [A[0]]
    for i in range(N-1):
        print(B)
        if A[i+1] >= B[-1]:
            B.append(A[i+1])
        else:
            index = bisect.bisect_right(B, A[i+1])
            B[index] = A[i+1]
    print(B)
    return B[::-1]


print(len(LDS(A)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect

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

def LIS(A):
    """
    returns Longest Increasing Subsequence of list A.
    """
    B = [A[0]]
    for i in range(N-1):
        if A[i+1] >= B[-1]:
            B.append(A[i+1])
        else:
            index = bisect.bisect_left(B, A[i+1])
            B[index] = A[i+1]
    return B

def LDS(A):
    """
    returns Longest decreasing Subsequence of list A.
    """
    A = A[::-1]
    B = [A[0]]
    for i in range(N-1):
        if A[i+1] >= B[-1]:
            B.append(A[i+1])
        else:
            index = bisect.bisect_left(B, A[i+1])
            B[index] = A[i+1]
    return B[::-1]


print(len(LDS(A)))

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
ans = []
for a in A:
    i = bisect.bisect(ans,a) #bisect.bisect_rightと同じ
    if i != len(ans):
        ans[i] = a
    else:
        ans.append(a)
print(len(ans))

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = [int(input()) for i in range(N)]
ans = []
for a in A:
    i = bisect.bisect(ans,a)
    print(i)
    if i != len(ans):
        ans[i] = a
        print(ans)
    else:
        ans.append(a)
        print(ans)
print(len(ans))

Submission status: Wrong Answer

Solution code:
# ABC134E - Sequence Decomposing
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    A = tuple(map(int, [input().rstrip() for _ in range(n)]))
    ans, cur = 0, float("inf")
    for i in A:
        if i <= cur:
            cur = i
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

for i in range(1,n):
  tmpmin = tree[0]
  if a[i] <= tmpmin:
    bisect.insort(tree, a[i])
  else:
    index = bisect.bisect_right(tree, a[i])
    del tree[index - 1]
    bisect.insort(tree, a[i])
    
print(len(tree))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from bisect import*
n,*a=map(int,open(0))
b=bisect
c=[-1]*n
for a in a:c[b(c,a-1)-1]=a
print(n-b(c,1))

Submission status: Wrong Answer

Solution code:
from bisect import*
n,*a=map(int,open(0))
b=bisect
c=[-1]*n
for a in a:c[b(c,a-1)-1]=a
print(n-b(c,0))

Submission status: Wrong Answer

Solution code:
import io
import sys
from bisect import bisect_right, bisect_left


def IN_S():
  return input()


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


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


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


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


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


test_str = '''
7
1
0
3
4
1
2
1
'''


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


def A():
  n = IN_I()

  l = [IN_I()]

  for i in range(0, n - 1):
    num = IN_I()

    idx = bisect_left(l, num)
    if idx == 0:
      l.insert(0, num)
    else:
      l[idx - 1] = num
    print(l)

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Wrong Answer

Solution code:
import io
import sys
from bisect import bisect_right


def IN_S():
  return input()


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


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


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


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


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


test_str = '''
7
1
0
3
4
1
2
1
'''


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


def A():
  n = IN_I()

  l = [IN_I()]

  for i in range(0, n - 1):
    num = IN_I()

    idx = bisect_right(l, num)

    # print(idx, l, num)
    if idx == len(l):
      if l[idx - 1] == num:
        l.insert(idx, num)
      else:
        l[idx - 1] = num
    elif idx == 0:
      l.insert(idx, num)
    else:
      l[idx - 1] = num
    # print(l)

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []

def dp(a):
    len_a = len(A)
    if len_a == 0:
        A.append(a)
    elif len_a == 1:
        if A[0] > a:
            A.append(a)
        else:
            A.insert(0,a)
    else:
        left = 0
        right = len_a-1
        while left < right:
            mid = (left+right)//2
            if a == A[mid]:
                A.insert(mid,a)
                return
            elif a > A[mid]:
                while a > A[mid] and mid >= 0:
                    mid -= 1
                mid += 1
                A[mid] = a
                return
            else:
                left = mid + 1
                mid = (left+right)//2
        if a < A[mid]:
            A.append(a)
        elif a == A[mid]:
            A.insert(mid,a)

for _ in range(N):
    a = int(input())
    dp(a)

print(len(A))

Submission status: Wrong Answer

Solution code:
import io
import sys
from math import ceil


def IN_S():
  return input()


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


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


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


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


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


test_str = '''
7
1
0
3
4
1
2
1
'''


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


def A():
  n = IN_I()

  l = [IN_I()]

  for i in range(0, n - 1):
    num = IN_I()

    if l[0] >= num:
      l.insert(0, num)
      continue

    inl = 0
    inr = len(l) - 1
    # 1, 2, 3, 4, 5
    for j in range(0, len(l)):
      if inr == inl:
        l[inr] = num
        break

      mid = ceil((inr - inl) / 2)
      if l[mid] >= num:
        inr = mid - 1
      else:
        inl = mid
    # print(l)

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Wrong Answer

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

def dp(a):
    len_a = len(A)
    if len_a == 0:
        A.append(a)
    elif len_a == 1:
        if A[0] > a:
            A.append(a)
        elif A[0] == a:
            A.insert(0,a)
    else:
        left = 0
        right = len_a-1
        while left < right:
            mid = (left+right)//2
            if a == A[mid]:
                A.insert(mid,a)
                return
            elif a > A[mid]:
                while a > A[mid] and mid >= 0:
                    mid -= 1
                mid += 1
                A[mid] = a
                return
            else:
                left = mid + 1
                mid = (left+right)//2

for _ in range(N):
    a = int(input())
    dp(a)

print(len(A))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC134 E

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n = int(input())
a = [int(input()) for _ in range(n)]
b = []
c = sorted(a)
for i in range(n):
    b.append([a[i],i])
b.sort(key = itemgetter(0))
x = [False]*n
ans = 0
for i in range(n):
    if x[i]:
        continue
    if x[i] == False:
        x[i] = True
        ans += 1
        r = bisect.bisect_right(c,a[i])
        for j,k in b[r:]:
            x[k] = True
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = [-int(input()) for _ in range(N)]
tmp = [A[0]]
for i in A[1:N]:
    index = bisect.bisect(tmp, i)
    if index == 0:
        tmp.append(i)
    else:
        tmp[index-1] = i

print(len(tmp))

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = [-int(input()) for _ in range(N)]
tmp = [A[0]]
for i in A[1:N]:
    index = bisect.bisect_left(tmp, i)
    if index == 0:
        tmp.append(i)
    else:
        tmp[index-1] = i

print(len(tmp))

Submission status: Wrong Answer

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

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


LIS = list()
for i in a:
    j = bisect.bisect_right(LIS, i)
    if len(LIS) == j:
        LIS.append(i)
    else:
        LIS[j] = i

print(len(LIS))

Submission status: Wrong Answer

Solution code:
N = int(input())
num_line = [int(input()) for _ in range(N)]
count = 1
first_num = num_line[0]
for i in range(1, N):
    if num_line[i] <= first_num:
        first_num  = num_line[i]
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
tmp = [A[0]]
for i in range(1, N):
    index = bisect.bisect_right(tmp, A[i])
    if index == 0:
        tmp.insert(0, A[i])
    else:
        tmp[index-1] = A[i]

print(len(tmp))

Submission status: Wrong Answer

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

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


LIS = list()
for i in a:
    j = bisect.bisect_right(LIS, i)
    if len(LIS) <= j:
        LIS.append(i)
    else:
        LIS[j] = i

print(len(LIS))

Submission status: Wrong Answer

Solution code:
N = int(input())
m = pow(10,9) + 1
ans = 0
for i in range(N):
    a = int(input())
    if a <= m:
        ans += 1
        m = a
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect

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


increasing_column = list()
for i in a:
    j = bisect(increasing_column, i)
    if len(increasing_column) <= j:
        increasing_column.append(i)
    else:
        increasing_column[j] = i

print(n - len(increasing_column))

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
tmp = [A[0]]
for i in range(1, N):
    index = bisect.bisect_left(tmp, A[i])
    if index == 0:
        tmp.append(A[i])
    else:
        tmp[index-1] = A[i]

print(len(tmp))

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from collections import deque
from bisect import bisect_right, bisect_left
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    d = deque()
    for a in A:
        t = bisect_right(d, a)
        if t == 0:
            d.appendleft(a)
            continue
        if d[t-1] == a:
            t = bisect_left(d, a)
        if t == 0:
            d.append(a)
        else:
            d[t-1] = a
    print(len(d))
    print(d)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect

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


increasing_column = list()
for i in a:
    j = bisect(increasing_column, i)
    if len(increasing_column) == j:
        increasing_column.append(i)
    else:
        increasing_column[j] = i

print(n - len(increasing_column))

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
from collections import deque
from bisect import bisect_right, bisect_left
def main():
    N = int( input())
    A = [ int( input()) for _ in range(N)]
    d = deque()
    for a in A:
        t = bisect_right(d, a)
        if t == 0:
            d.append(a)
            continue
        if d[t-1] == a:
            t = bisect_left(d, a)
        if t == 0:
            d.append(a)
        else:
            d[t-1] = a
    print(len(d))
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
tmp = [A[0]]
ans = 0
for i in range(1, N):
    index = bisect.bisect_left(tmp, A[i])
    print(A[i], index)
    if index == 0:
        tmp.append(A[i])
        tmp.sort()
    else:
        tmp[index-1] = A[i]

print(len(tmp))

Submission status: Wrong Answer

Solution code:
N = int(input())
num_line = [int(input()) for _ in range(N)]
count = 1
first_num = num_line[0]
for i in range(1, N):
    if num_line[i] <= first_num:
        count += 1
print(count)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs,math,heapq as hq
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))

n = onem()

a = [onem() for i in range(n)]

d = [a[0]]
co = 1
for i in range(1,n):
	for j in range(len(d)):
		if d[-(j+1)] < a[i]:
			d.pop(-(j+1))
			d.insert(a[i],-(j+1))
			break
	else:
		co += 1
		d.append(a[i])
print(co)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
inf = float('inf')


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

color = [A[0]]
for a in A[1:]:
    pos = bisect_left(color, a)
    if pos == 0:
        color.insert(a,0)
    else:
        color[pos-1] = a

ans = len(color)
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
li = [-1]
len_ = 1
c = 1
b = -1
index = -1

ns = [int(input()) for _ in range(N)]
flag = 0
for n in ns:
    index = -1
    while n <= b:
        if flag:
            c += 1
            li.append(n)
            flag = 0
            break
        try:
            index -= 1
            b = li[index]
        except BaseException:
            c += 1
            li.append(n)
            flag = 1
            break
    li[index] = b = n

print(c)

Submission status: Wrong Answer

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

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