Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

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

Sample Input 1

5
2
1
4
5
3

Sample Output 1

2

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

Sample Input 2

4
0
0
0
0

Sample Output 2

4

We have to paint all the integers with distinct colors.



Sample input:
5
2
1
4
5
3


Sample output:
2

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import heapq
import bisect

def main():
    N = int(input())
    l = []

    for i in range(N):
        a = int(input())
        if len(l) == 0 or a <= l[0]:
            heapq.heappush(l, a)
        else:
            ind = bisect.bisect_left(l, a)
            l[ind-1] = a
    print(len(l))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import bisect

def main():
    N = int(input())
    l = []

    for i in range(N):
        a = int(input())
        if len(l) == 0 or a <= l[0]:
            heapq.heappush(l, a)
        else:
            ind = bisect.bisect_right(l, a)
            l[ind-1] = a
    print(len(l))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
l = []

for i in range(N):
    a = int(input())
    ind = bisect.bisect_right(l, a)
    if ind == 0 or a == l[0]:
        bisect.insort_left(l, a)
    else:
        l[ind-1] = a
print(len(l))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
ans = 0
m = 10**10
for i in range(N):
    if m >= A[i]:
        m = A[i]
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ans = 1
for i in range(n):
    a = int(input())
    if i == 0:
        cnt = a
    elif cnt >= a:
        ans += 1
        cnt = a
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
A=[]
ans=0
for i in range(N):
    a=int(input())
    A.append(a)
cl=[A[-1]]
ans=1
for i in range(N-1)[::-1]:
    a=A[i]
    if a>=cl[-1]:
        cl.append(a)
        ans+=1
    else:
        b=bisect.bisect_left(cl,a)
        cl[b]=a
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left

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())

    A.reverse()

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

    print(len(dp))
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from bisect import bisect

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

dp = []
for a in A[::-1]:
    i = bisect(dp, a)
    if i < len(dp):
        dp[i] = a
    else:
        dp.append(a)
print(len(dp))

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
ais = [int(raw_input()) for _ in range(n)]
tails = []
import bisect
for a in ais:
	if not(tails) or (tails[-1] > a):
		tails.append(a)
	else:
		# maintain a decreaing tails
		986643321
		lo,hi = 0, len(tails) - 1
		while(lo<hi):
			med= (lo + hi)/2
			if tails[med] < a:
				hi = med
			else:
				lo = med + 1
		tails[lo] = a
print len(tails)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
ais = [int(raw_input()) for _ in range(n)]
tails = []
import bisect
for a in ais:
	if not(tails) or tails[0] > a:
		tails = [a] + tails 
	else:
		ii = 0
		while(ii < len(tails)):
			if tails[ii] > a:
				break
			ii +=1
		tails[ii-1] = a
	
print len(tails)

Submission status: Wrong Answer

Solution code:
#最長増加部分列問題 (LIS) 
import bisect

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

LIS = []
#print(LIS)
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

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

  #print(LIS)
print(len(LIS))

Submission status: Wrong Answer

Solution code:
#最長増加部分列問題 (LIS) 
import bisect

N = int(input())
seq = [0] * N
for i in range(N):
  seq[i] = N + 1 - int(input())

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

    #print(LIS)
print(len(LIS))

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = [int(input()) for _ in range(n)]
    ans = 0
    dic = defaultdict(int)
    for ai in a:
        for i in range(n):
            if dic[i] < ai:
                dic[i] = ai
                break

    print(len(dic))


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = [int(input()) for _ in range(n)]
    ans = 0
    min = float('inf')
    dic = defaultdict(int)
    for ai in a:
        dic[ai] += 1
        if ai <= min:
            ans += 1
            min = ai
        elif dic[ai] > ans:
            ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = [int(input()) for _ in range(n)]
    ans = 0
    min = float('inf')
    for ai in a:
        if ai <= min:
            ans += 1
            min = ai
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
import bisect


def solve(N, As):
    colors = []
    for a in As:
        if not colors:
            colors.append(a)
        else:
            if a <= colors[0]:
                colors.insert(a, 0)
            else:
                i = bisect.bisect_left(colors, a)
                colors[i - 1] = a
                j = i - 1
                while j + 1 < len(colors) and colors[j] > colors[j + 1]:
                    colors[j], colors[j + 1] = colors[j + 1], colors[j]
                    j += 1
    return len(colors)


if __name__ == "__main__":
    N = int(input())
    As = []
    [As.append(int(input())) for i in range(N)]
    print(solve(N, As))

Submission status: Wrong Answer

Solution code:
import bisect

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

dp = [float("inf")] * (N+1)
dp[0] = -1
dp[1] = A[0]

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

for i in reversed(range(N+1)):
    if dp[i] < float("inf"):
        print(i)
        break

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**10

    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる
        
        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき
            
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)

        def print(self):
            print(self.layer1)
            print(self.layer0)
            
        def len(self):
            return len(self.layer0[0])
    ##############################

        

            
    N=I()
    A=[0]*N
    
    for i in range(N):
        A[i]=I()
        
    ssl = SquareSkipList(square=2000)
    ssl.add(-1)#初期値入れとこ
    
    for i in range(N):
        a=A[i]
        m=ssl.search_lower(a)
        if m==-1:
            ssl.add(a)
        else:
            ssl.remove(m)
            ssl.add(a)
            
    print(ssl.len()-1)
    



main()

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
INF = (10**5)+1
A = {}
for i in range(N):
    a = int(input())
    A[i] = a

B = [A[N-1]]
for i in range(N-2,-1,-1):
    a = A[i]
    if B[-1] <= a:
        B.append(a)
    else:
        B[bisect.bisect_left(B,a)] = a



print(len(B))

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
INF = (10**5)+1
A = []
for i in range(N):
    a = int(input())
    A.append(a)

B = [A[-1]]
for i in range(N-2,-1,-1):
    a = A[i]
    if B[-1] > a:
        del B[-1]
        bisect.insort_left(B,a)
    else:
        bisect.insort_left(B,a)



print(len(B))

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import bisect
def make_LIS(L):
    LIS=[L[0]]
    for i in range(1,len(L)):
        if L[i]>=LIS[-1]:#広義単調増加なら>=に
            LIS.append(L[i])
        else:
            LIS[bisect.bisect_left(LIS,L[i])]=L[i]
    return len(LIS)
def main():
    n=int(input())
    A=[int(input())for _ in range(n)]
    print(make_LIS(A[::-1]))

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
my_max = []
heapq.heapify(my_max)
prev = -1
ans = 1
for _ in range(N):
    a = int(input())
    if a <= prev:
        heapq.heappush(my_max, prev)
        if my_max[0] < a:
            heapq.heappop(my_max)
            heapq.heappush(my_max, a)
        else:
            ans += 1
    prev = a
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
N = int(input())
my_max = []
heapq.heapify(my_max)
prev = -1
ans = 1
for _ in range(N):
    a = int(input())
    if a <= prev:
        heapq.heappush(my_max, prev)
        if my_max[0] < a:
            heapq.heappop(my_max)
            heapq.heappush(my_max, a)
        else:
            ans += 1
            prev = a
    else:
        prev = a
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
As = [int(input()) for _ in range(N)]
from bisect import bisect_left
from collections import deque

def LIS(L):
    dp = deque([L[0]])
    length = len(L)
    for i in range(1, length):
        a = L[i]
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_left(dp, a)] = a
    return dp

print(len(LIS(As[::-1])))

Submission status: Wrong Answer

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

def LIS(L):
    dp = [L[0]]
    length = len(L)
    for i in range(1, length):
        print(dp)
        a = L[i]
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_left(dp, a)] = a
    return dp

print(len(LIS(As[::-1])))

Submission status: Wrong Answer

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

def LIS(L):
    dp = [L[0]]
    length = len(L)
    for i in range(1, length):
        a = L[i]
        if a <= dp[0]:
            dp.insert(0, a)
        else:
            dp[bisect_right(dp, a)-1] = a
    return dp

print(len(LIS(As)))

Submission status: Wrong Answer

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

def LIS(L):
    dp = [L[0]]
    length = len(L)
    for i in range(1, length):
        a = L[i]
        if a <= dp[0]:
            dp.insert(0, a)
        else:
            dp[bisect_right(dp, a)-1] = a
    return dp

print(len(LIS(As)))

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque

n = int(input())
lis = deque()

ans = 0
for i in range(n):
    a = int(input())
    if i == 0:
        lis.append(a)
        continue
    l = bisect.bisect_left(lis,a)
    r = bisect.bisect_right(lis,a)
    if l != r:#同じものがある
        lis.append(a)
        lis = deque(sorted(list(lis)))
    elif l == 0:#最小値追加
        lis.appendleft(a)
    else:#最大値更新
        lis[r-1] = a
print(len(lis))

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque

n = int(input())
lis = deque()

ans = 0
for i in range(n):
    a = int(input())
    if i == 0:
        lis.append(a)
        continue
    l = bisect.bisect_left(lis,a)
    r = bisect.bisect_right(lis,a)
    if l != r:#同じものがある
        ans+=1
    elif l == 0:
        lis.appendleft(a)
    else:
        lis[l-1] = a
print(len(lis)+ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import bisect_left
N=int(input())
li=[]
ans=0
for i in range(N):
    a=-int(input())
    b=bisect_left(li,a+1)
    if b==len(li):
        li.append(a)
        ans+=1
    else:
        li[b]=a
    print(li)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque
def LIS(a):
    lis = deque()
    lis.append(-1)
    for i in range(len(a)):
        index = bisect.bisect_left(lis,a[i])
        if i == 0:
            lis.appendleft(a[i])
        else:
            lis[index-1] = a[i]
    return len(lis)

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    print(LIS(a))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
def LIS(a):
    lis = [a[0]]
    for i in range(len(a)):
        if i != 0 and a[i] >= lis[-1]:
            lis.append(a[i])
        else:
            index = bisect.bisect_left(lis,a[i])
            lis[index] = a[i]
    return len(lis)

def main():
    n = int(input())
    a = [-int(input()) for _ in range(n)]
    print(LIS(a))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
def LIS(a): #最長増加部分列
    lis = [a[0]]
    cnt = 0
    for i in range(len(a)):
        if a[i] > lis[-1]:
            lis.append(a[i])
        else:
            index = bisect.bisect_left(lis,a[i])
            lis[index] = a[i]
            if index == 0:
                cnt += 1
    return cnt

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    print(LIS(a))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
m=10**10
ans=0
for i in range(n):
    a=int(input())
    if a<=m:
        m=a
        ans+=1
print(ans)

Submission status: Wrong Answer

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

stk = []
ret = 0

for item in a:
    while stk and stk[-1] < item:
        stk.pop()
    stk.append(item)
    if len(stk) > ret:
        ret = len(stk)

print(ret)

Submission status: Wrong Answer

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

stk = []
ret = 0

for item in a:
    if not stk:
        stk.append(item)
        if len(stk) > ret:
            ret = len(stk)
    else:
        while stk and stk[-1] < item:
            stk.pop()
        stk.append(item)
        if len(stk) > ret:
            ret = len(stk)

print(ret)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

q = []
for _ in range(n):
    a = int(input())
    if len(q)==0:
        heapq.heappush(q, -a)
    else:
        if -q[0]<a:
            heapq.heappushpop(q,-a)
        else:
            heapq.heappush(q,-a)

print(len(q))

Submission status: Wrong Answer

Solution code:
ans = 0
ansi = 1
N = int(input())
now = int(input())
for _ in range(1,N):
    a = int(input())
    if now < a:
        ans = max(ans, ansi)
        ansi = 1
    else:
        ansi += 1
    now = a
ans = max(ans, ansi)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

Color = []
N = int(input())
for _ in range(N):
    a = int(input())
    if len(Color) == 0:
        Color.append(a)
    elif Color[0] >= a:
        heapq.heappush(Color, a)
    else:
        for i in range(1,len(Color)+1):
            if Color[-i] < a:
                Color[-i] = a
                break

print(len(Color))

Submission status: Wrong Answer

Solution code:
def LIS(l):
    from bisect import bisect_left
    dp = [l[0]+1]
    for i in range(len(l)):
        if l[i] >= dp[-1]:
            dp.append(l[i])
        else:
            dp[bisect_left(dp, l[i])] = l[i]
    return len(dp)
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    print(LIS(a[::-1]))
main()

Submission status: Wrong Answer

Solution code:
import bisect
N, *A = map( int, open( 0 ).read().split() )
L = [ A[ 0 ] ]
for a in A[1:]:
  kr = bisect.bisect_right( L, a )
  if ( kr != 0 ) and ( a != L[ kr -1 ] ):
    L[ kr - 1 ] = a
  else:
    L.insert( kr, a )
print( len( L ) )

Submission status: Wrong Answer

Solution code:
import bisect
N, *A = map( int, open( 0 ).read().split() )
L = [ A[ 0 ] ]
for a in A[1:]:
  kr = bisect.bisect_right( L, a )
  print( kr, a )
  if ( kr != 0 ) and ( a != L[ kr -1 ] ):
    L[ kr - 1 ] = a
  else:
    L.insert( kr, a )

print( len( L ) )

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
Minimum = [A[0]]
def Search(S,i):
    num = len(S)//2
    if i <= S[num-1]:
        return Search(S[:num],i)
    elif S[num-1] < i and i <= S[num]:
        return num
    else:
        return num + Search(S[num:],i)
for i in range(1,N):
    if A[i] <= Minimum[0]:
        Minimum = [A[i]]+Minimum
    elif A[i] > Minimum[len(Minimum)-1]:
        Minimum[len(Minimum)-1] = A[i]
    else:
        Minimum[Search(Minimum,A[i])] = A[i]
print(len(Minimum))

Submission status: Wrong Answer

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

import bisect

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

A.reverse()
INF = float('inf')
dp = [INF for _ in range(N)]

for a in A:
    target_index = bisect.bisect_right(dp, a)
    print(a, target_index)
    dp[target_index] = a

# print(dp)
print(bisect.bisect_left(dp, INF))

Submission status: Wrong Answer

Solution code:
from collections import deque

n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
l=deque([a[0]])
for i in range(1,n):
    if l[0]>=a[i]:
        l.appendleft(a[i])
    elif l[-1]<=a[i]:
        l[-1]=a[i]
    else:
        p=0
        q=len(l)-1
        while q-p!=1:
            if l[(p+q)//2]>=a[i]:
                q=(p+q)//2
            else:
                p=(p+q)//2
        l[p]=a[i]
print(len(l))

Submission status: Wrong Answer

Solution code:
from collections import deque

n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
l=deque([a[0]])
for i in range(1,n):
    if l[0]>=a[i]:
        l.appendleft(a[i])
    elif l[-1]<=a[i]:
        l.append(a[i])
    else:
        p=0
        q=len(l)-1
        while q-p!=1:
            if l[(p+q)//2]>=a[i]:
                q=(p+q)//2
            else:
                p=(p+q)//2
        l[p]=a[i]
print(len(l))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n):
    A=int(input())
    a.append(A)
a.append(a[n-1]+1)
l=[0]
for i in range(n):
    if a[i]>=a[i+1]:
        if l[0]<a[i]:
            l[0]=a[i]
        else:
            l.append(a[i])
    else:
        continue
if l[0]==0:
    print(len(l))
else:
    print(len(l)+1)

Submission status: Wrong Answer

Solution code:
n = int(input())

colors = []

for i in range(n):
  a = int(input())
  if i == 0:
    colors.append(a)
    continue
  if colors[-1] >= a:
    colors.append(a)
  elif a > colors[0]:
    colors[0] = a
  else:
    l, r = 0, len(colors)
    while r-l > 1:
      k = (r+l)//2
      if a > colors[k]:
        l = k
      else:
        r = k
    if a > colors[l]:
      colors[l] = a
    else:
      colors[r] = a

print(len(colors))

Submission status: Wrong Answer

Solution code:
n = int(input())

colors = []

for i in range(n):
  a = int(input())
  if i == 0:
    colors.append(a)
    continue
  if a <= colors[-1]:
    colors.append(a)
  elif a > colors[0]:
    colors[0] = a
  else:
    l, r = 0, len(colors)
    while r-l > 1:
      k = (r+l)//2
      if colors[k] >= a:
        r = k
      else:
        l = k
    if colors[l] < a:
      colors[l] = a
    else:
      colors[r] = a

print(len(colors))

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
import heapq

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color = [A[0]]
    heapq.heapify(color)

    for i in range(1, N):
        idx = bisect_left(color, A[i])
        if idx == 0:
            heapq.heappush(color, A[i])
        else:
            color[idx - 1] = A[i]

    print(len(color))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_right

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    color = [A[0]]

    for i in range(1, N):
        idx = bisect_right(color, A[i])
        if idx == 0:
            color = [A[i]] + color
        else:
            color[idx - 1] = A[i]

    print(len(color))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
color = 0
a = int(input())
for i in range(1,N):
  b = int(input())
  if a >= b:
    color += 1
    
  a = b
  
print(color)

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
LIS = [-1 * int(input())]
for _ in range(N-1):
    A = -1 * int(input())
    if A >= LIS[-1]:
        LIS.append(A)
    else:
        LIS[bisect.bisect_left(LIS, A)] = A

print(len(LIS))

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
LIS = [int(input())]
for _ in range(N-1):
    A = -1 * int(input())
    if A >= LIS[-1]:
        LIS.append(A)
    else:
        LIS[bisect.bisect_left(LIS, A)] = A

print(len(LIS))

Submission status: Wrong Answer

Solution code:
n=int(input())
v=[int(input()) for i in range(n)]
c=1
m=v[0]
for i in range(1,n):
  if v[i]<m: c+=1;m=v[i]
print(c)

Submission status: Wrong Answer

Solution code:
import bisect

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

R=[A[0]]
R_set=set(R)

for j in range(1,N):
    if A[j] in R_set:
        bisect.insort(R,A[j])
    else:
        index=bisect.bisect(R,A[j])
        if index==0:
            bisect.insort(R,A[j])
        else:
            R[index-1]=A[j]
            R_set.add(A[j])
    #print(R)

print(len(R))

Submission status: Wrong Answer

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
infi = 10 ** 20

n, *A = map(int, read().split())
LIS = deque([10 ** 10])
for a in A:
    a *= -1
    pos = bisect_left(LIS, a)
    if LIS[-1] <= a:
        LIS.append(a)
    else:
        if LIS[pos] == a:
            if pos == 0:
                LIS.appendleft(a)
            else:
                LIS[pos - 1] = a
        else:
            LIS[pos] = a

print(len(LIS))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

LIS = [10 ** 10 + 5]
n, *A = map(int, read().split())

for a in A:
    temp = 10 ** 10 - a
    if LIS[-1] <= temp:
        LIS.append(temp)
    else:
        pos = bisect_left(LIS, temp)
        LIS[pos] = temp
print(len(LIS))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

LIS = [1]
n, *A = map(int, read().split())

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

LIS = [1]
n, *A = map(int, read().split())

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

Submission status: Wrong Answer

Solution code:
n=int(input())
seq=[int(input()) for i in range(n) ][::-1]


import bisect

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]

ans=len(LIS)
if ans==1:
    print(n)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = []
maximum = 0
minimum = float('inf')
count = 0
for i in range(N):
    a = int(input())
    A.append(a)
    maximum = max(maximum,a)
    if a <= minimum:
        minimum = a
        count += 1
c = Counter(A)
print(max(count,max(c.values())))

Submission status: Wrong Answer

Solution code:
import bisect

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

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = [int(input()) for _ in range(N)]
counter = Counter(A)
if counter.most_common()[0][0] >= N//2:
    print(counter.most_common()[0][0])
    exit()
ans = 0
while True:
    tmp = -1
    for i in range(N):
        if A[i] > tmp:
            tmp = A[i]
            A[i] = -1
    if tmp == -1:
        break
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n):
  ai=int(input())
  a.append(ai)
b=[a[n-1]]
ans=1
for i in reversed(range(n-1)):
  if a[i]>=b[-1]:
    b.append(a[i])
    ans=ans+1
  else:
    for j in range(ans):
      if j>a[i]:
        j=a[i]
        break
print(ans)