Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

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

Sample Input 1

5
2
1
4
5
3

Sample Output 1

2

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

Sample Input 2

4
0
0
0
0

Sample Output 2

4

We have to paint all the integers with distinct colors.



Sample input:
5
2
1
4
5
3


Sample output:
2

Submission status: Wrong Answer

Solution code:
import bisect
def LIS():
    L[0] = A[0]
    length = 1
    for i in range(1, N):
        if L[length] < A[i]:
            length += 1
            L[length] = A[i]
        else:
            j = bisect.bisect_left(L, A[i])
            L[min(length-1, j)] = A[i]
        return length

def LISDesc():
    L[-1] = A[-1]
    length = 1
    for i in range(N-2, 0, -1):
        if L[N-length] <= A[i]:
            length += 1
            L[N-length] = A[i]
        else:
            j = bisect.bisect_right(L, A[i])
            L[min(N-(length-1), j)] = A[i]
    return length

INFTY = 10**13
N = int(input())
A = [int(input()) for i in range(N)]
L = [-1 for i in range(N)]
ans = LISDesc()
print(ans)

Submission status: Wrong Answer

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

import math

if __name__ == '__main__':
    N = int(input())
    A = []
    for i in range(N):
        A.append(
            [int(input()), -1]
        )
    color = 0
    # R = [0 for i in range(N)]
    # M = 0

    for i in range(N-1, -1, -1):
        # print('i={}'.format(i))
        if A[i][1] != -1:
            continue

        current = A[i][0]
        A[i][1] = color

        for j in range(i - 1, -1, -1):
            if A[j][0] < current and A[j][1] == -1:
                A[j][1] = color

        color += 1

    print(color)

Submission status: Wrong Answer

Solution code:
import bisect

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

for i in range(N):
    hoge = bisect.bisect_left(result,S[i])
    if hoge == 0:
        result.append(S[i])
    else:
        result[hoge - 1] = S[i]
print(len(result))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bl

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

def lis(X: list):
    L = [-X[0]]
    for x in X[1:]:
        if L[-1] <= -x:
            L.append(-x)
        else:
            L[bl(L, -x)] = -x
    return len(L)

print(lis(A))

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = 1
ans = 0
tmp = int(input())
for i in range(1,N):
    A = int(input())
    if A <= tmp:
        memo += 1
    elif ans < memo:
        ans = memo
        memo = 0
    else:
        memo = 0
    tmp = A
ans = max(ans,memo)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = 0
ans = 0
tmp = int(input())
for i in range(1,N):
    A = int(input())
    if A <= tmp:
        memo += 1
    elif ans < memo:
        ans = memo
        memo = 0
    else:
        memo = 0
    tmp = A
ans = max(ans,memo)
print(ans+1)

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = 0
ans = 0
tmp = int(input())
for i in range(1,N):
    A = int(input())
    if A <= tmp:
        memo += 1
    elif ans < memo:
        ans = memo
        memo = 0
    else:
        memo = 0
    tmp = A
ans = max(ans,memo)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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


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)

print(lis(X))

Submission status: Wrong Answer

Solution code:
import bisect


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

print(len(LIS))

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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


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

print(len(LIS))

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = 0
ans = 0
tmp = int(input())
for i in range(1,N):
    A = int(input())
    if A <= tmp:
        tmp = A
        memo += 1
    elif ans < memo:
        ans = memo
        memo = 0
    else:
        memo = 0
    tmp = A
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
vi={}
for i,v in enumerate(sorted(set(A))):
    vi[v]=i
B=[0]*N
for i,a in enumerate(A):
    B[i]=vi[a]+1
A=B

class SegmentTree():
    def __init__(self, array, f, e, size):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
        """
        self.f = f
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = dat = [e] * n + array + [e] * (2 * size - 2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = f(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, e, n, dat = self.f, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(res, dat[r])
            l >>= 1
            r >>= 1
        return res


size = 10**5+5
e = (0,0)
def f2(xs,ys):
    if ys[0]>0:
        return ys
    else:
        return xs
ST = SegmentTree(list(zip([size]+[0]*(size-1),range(size))), f=lambda x,y:f2(x,y), e=e, size=size)
ans = 0
for a in A:
    bs = ST.query(0,a)
    if bs[1]==0:
        c=ST.query(a,a+1)[0]
        ST.modify(a,(c+1,a))
        ans+=1
    else:
        c=ST.query(a,a+1)[0]
        ST.modify(a,(c+1,a))
        ST.modify(bs[0],(bs[0],bs[1]-1))
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for _ in range(n):
  a.append(int(input()))
sit = 0
small = 10 ** 6
count = 0
while sit < n:
  if small >= a[sit]:
    small = a[sit]
    count += 1
  sit += 1
print(count)

Submission status: Wrong Answer

Solution code:
len_arr = int(input())

arr = [int(input()) for _ in range(0, len_arr)]

current_min = {arr[-1]: 1}
num_color = 1

for i in reversed(range(0, len_arr-1)):
    target = arr[i]
    current_set = current_min.keys()
    # print(current_min)
    m = max(current_set)

    if target >= m:
        num_color += 1
        if target == m:
            current_min[target] += 1
        else:
            current_min[target] = 1
    else:
        acceptable = [x for x in current_set if x > target]
        # print(acceptable)
        selected = min(acceptable)

        if current_min[selected] == 1:
            del(current_min[selected])
            if target in current_set:
                current_min[target] += 1
            else:
                current_min[target] = 1

        else:
            current_min[selected] -= 1

print(num_color)
exit(0)

Submission status: Wrong Answer

Solution code:
import numpy as np
  
N = int(input())  
A = np.zeros(N)
B = np.zeros(N)
B[0] = 1

for i in range(N):
    A[i] = int(input())
    
for i in np.arange(N-1)+1:
    if A[i] > A [i-1]:
        B[i] = 1
        
K = np.where(B == 1)[0]
K = np.append(K, N)
C = np.zeros(K.size-1)

for i in np.arange(K.size-1):
    C[i] = K[i+1] - K[i]
    
print(int(np.max(C)))

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict
import sys
import bisect
input = sys.stdin.readline

n = int(input())
#####単位元######
ide_ele = -1
#ide_ele = 10**9+1

#num:n以上の最小の2のべき乗
num =2**((n-1).bit_length())
seg=[ide_ele]*(2*num)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res
    
def main():
    used = defaultdict(int)
    aa = [int(input()) for i in range(n)]
    b = sorted(aa)
    for i in range(n):
        aa[i] = bisect.bisect_left(b,aa[i])
    a0 = aa[0]
    tank = [a0]
    used[a0] = 1
    update(a0,a0)
    
    for i in range(1,n):
        a = aa[i]
        while True:
            if used[tank[0]] > 0:
                break
            else:
                heapq.heappop(tank)
        #塗り替え
        if tank[0] < a:
            ma = query(0,a)

            used[ma] -= 1
            heapq.heappush(tank,a)
            used[a] += 1
            if used[ma] == 0:
                update(ma,-1)
        else:
            heapq.heappush(tank,a)
            used[a] += 1
        update(a,a)

    res = 0
    for e in tank:
        if used[e] > 0:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
  
N = int(input())  
A = np.zeros(N)
B = np.zeros(N)
B[0] = 1

for i in range(N):
    A[i] = int(input())
    
for i in np.arange(N-1)+1:
    if A[i] > A [i-1]:
        B[i] = 1
        
K = np.where(B == 1)[0]
K = np.append(K, N-1)
C = np.zeros(K.size-1)

for i in np.arange(K.size-1):
    C[i] = K[i+1] - K[i]
    
print(int(np.max(C)))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import deque

fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = deque([A[0]])#常に小さい順にソートされている
surfMax = A[0]
surfMin = A[0]
color = 1
for n,a in enumerate(A):
    if n==0:continue

    if color == 1:
        c = surface[0]
        if a>c:
            surface[0] = a
            surfMax = a
            surfMin = a
        if a==c:
            surface.append(a)
            color += 1
        if a<c:
            surface.append(a)
            color += 1
            surfMin = a

    else:    
        if a<=surfMin:
            color += 1
            surface.appendleft(a)
            surfMin = a
        elif a>surfMax:
            surface[color-1] = a
            surfMax = a
        else:
            pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
            surface[pos] = a
            if pos==0:
                surfMin = a
            if pos == color-1:
                surfMax = a
print(color)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(input()) for i in range(n)]
#print(n,l)

L = 0
cnt = 0
for i in range(n):
    if i == 0:
        cnt += 1
    elif l[i-1] >= l[i]:
        cnt += 1
    else:
        cnt = 0
    if L <= cnt:
        L = cnt
print(L)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
n = int(input())
count = 0
ans = 0
for i in range(n):
    a = int(input())
    if count==0:
        count += 1
        prev = a
        #continue
    elif prev >= a:
        prev = a
        count += 1
        #continue
    else:
        if ans < count: 
            ans = count
        count = 0
if ans < count:
    ans = count

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[]
for i in range(n):
    x=int(input())
    arr.append(x) 
ans=[0]*(n)
cc=1
ans[0]=arr[0]
for i in range(1,n):
    if arr[i]<=ans[-1]:
        ans[cc]=arr[i]
        cc+=1 
    else:
        start=0
        end=len(ans)-1 
        # pos=-1 
        pos=end 
        while start<=end:
            mid=(start+end)>>1 
            if arr[mid]<arr[i]:
                pos=mid 
                end=mid-1 
            else:
                start=mid+1 
        ans[pos]=arr[i]
# print(ans)
print(cc)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import deque

fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = deque([A[0]])#常に小さい順にソートされている
surfMax = A[0]
surfMin = A[0]
color = 1
for n,a in enumerate(A):
    if n==0:continue

    if color == 1:
        c = surface[0]
        if a>c:
            surface[0] = a
            surfMax = a
            surfMin = a
        if a==c:
            surface.append(a)
            color += 1
        if a<c:
            surface.append(a)
            color += 1
            surfMax = a
            surfMin = a

    else:    
        if a<=surfMin:
            color += 1
            surface.appendleft(a)
            surfMin = a
        elif a>surfMax:
            surface[color-1] = a
            surfMax = a
        else:
            pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
            surface[pos] = a
            if pos==0:
                surfMin = a
            if pos == color-1:
                surfMax = a
print(color)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import deque

fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = deque([A[0]])#常に小さい順にソートされている
surfMax = A[0]
surfMin = A[0]
color = 1
for n,a in enumerate(A):
    if n==0:continue

    if color == 1:
        c = surface[0]
        if a>c:
            surface[0] = a
            surfMax = a
            surfMin = a
        if a==c:
            surface.append(a)
            color += 1
        if a<c:
            surface.append(a)
            color += 1
            surfMax = a
            surfMin = a
        print(surface)

    else:    
        if a<=surfMin:
            color += 1
            surface.appendleft(a)
            surfMin = a
        elif a>surfMax:
            surface[color-1] = a
            surfMax = a
        else:
            pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
            surface[pos] = a
            if pos==0:
                surfMin = a
            if pos == color-1:
                surfMax = a
print(color)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[]
for i in range(n):
    x=int(input())
    arr.append(x) 
ans=[0]*(n)
cc=1
ans[0]=arr[0]
for i in range(1,n):
    if arr[i]<=ans[-1]:
        ans[cc]=arr[i]
        cc+=1 
    else:
        start=0
        end=len(ans)-1 
        pos=-1 
        while start<=end:
            mid=(start+end)>>1 
            if arr[mid]<arr[i]:
                pos=mid 
                end=mid-1 
            else:
                start=mid+1 
        ans[pos]=arr[i]
# print(ans)
print(cc)

Submission status: Wrong Answer

Solution code:

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

import bisect

color = []
color.append(a.pop(0))
color_count =0 
for i, ai in enumerate(a): 
    index = bisect.bisect_left(color, ai)
    if index > 0:
        color[index -1] = ai
    else:
        color.append(ai)
print(len(color))

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [int(input()) for i in range(n)]
mini = 10000000000
count = 0
for i in l:
    if i <= mini:
        count += 1
        mini = i
print(max(count,mini))

Submission status: Wrong Answer

Solution code:
def seek(value):
    right = len(color_list) - 1
    left = 0
    while(True):
        mid = (right + left) // 2
        if(value > color_list[mid]):
            right = mid
        else:
            left = mid
        if(right - left <= 1):
            return mid

N = int(input())    
color_list =  [int(input())]
for i in range(N-1):
    new_value = int(input())
    if(new_value > color_list[0]):
        color_list[0] = new_value
    elif(new_value <= color_list[-1]):
        color_list.append(new_value)
    else:
        new_index = seek(new_value)
        color_list[new_index] = new_value
print(len(color_list))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import deque

fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = deque([A[0]])#常に小さい順にソートされている
surfMax = A[0]
surfMin = A[0]
color = 1
for n,a in enumerate(A):
    if n==0:continue

    if color == 1:
        c = surface[0]
        if a>c:
            surfMax = a
            surfMin = a
        if a==c:
            surface.append(a)
            color += 1
        if a<c:
            surface.append(a)
            color += 1
            surfMax = a
            surfMin = a

    else:    
        if a<=surfMin:
            color += 1
            surface.appendleft(a)
            surfMin = a
        elif a>surfMax:
            surface[color-1] = a
            surfMax = a
        else:
            pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
            surface[pos] = a
            if pos==0:
                surfMin = a
            if pos == color-1:
                surfMax = a
print(color)

Submission status: Wrong Answer

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

# N: 処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

ans = 0

for i, a in enumerate(A):
    if a <= query(0,i):
        ans += 1
    update(i,a)

print(ans)

Submission status: Wrong Answer

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

for i in a:
    if t >= i:
        ans += 1
        t = i

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from operator import itemgetter, mul
from copy import deepcopy,copy
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n=INT()
    a = [INT() for _ in range(n)]
    ct=0
    tmp=1
    for i in range(1,n):
        if a[i] <= a[i-1]:
            tmp+=1
        else:
            ct=max(ct,tmp)
            tmp=1
    ct=max(ct,tmp)

    print(ct)

if  __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

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

print(len(L))

Submission status: Wrong Answer

Solution code:
len_arr = int(input())

arr = [int(input()) for _ in range(0, len_arr)]

current_min = {arr[-1]: 1}
num_color = 1

for i in reversed(range(0, len_arr-1)):
    target = arr[i]
    current_set = current_min.keys()
    # print(current_set)

    if target >= max(current_set):
        num_color += 1
        current_min[target] = 1
        current_max = target
    else:
        acceptable = [x for x in current_set if x > target]
        selected = min(acceptable)

        if current_min[selected] == 1:
            del(current_min[selected])

            if target in current_set:
                current_min[target] += 1
            else:
                current_min[target] = 1

        else:
            current_min[selected] -= 1

print(num_color)
exit(0)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import deque

fastinput = sys.stdin.readline
N = int(fastinput())
A = [int(fastinput()) for j in range(N)]
surface = deque([A[0]])#常に小さい順にソートされている
surfMax = A[0]
surfMin = A[0]
color = 1
for n,a in enumerate(A):
    if n==0:
        continue
    else:
        pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
        surface[pos] = a
        if pos==0:
            surfMin = a
        elif pos == -1:
            color += 1
            surface.appendleft(a)
        else:
            surface[pos] = a
print(color)

Submission status: Wrong Answer

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

A = sorted(A, key=lambda x: (x[1], -1 * x[0]))
# print(A)

import heapq
memo = [A[0][0]]
for a in A[1:]:
    num = a[0]
    smallest = heapq.heappop(memo)
    # print(smallest, num)
    if num < smallest:
        heapq.heappush(memo, num)
        heapq.heappush(memo, smallest)
    else:
        heapq.heappush(memo, num)

print(len(memo))

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 = []
c = 0
for i in range(n):
	a.append(onem())
aa = []
co = 0



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

Submission status: Wrong Answer

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

b = []
b.append(a[0])
cnt = 1
for i in range(n-1):
    if a[i] >= a[i+1]:
        if (len(b) > 1) and (b[-2] < a[i+1]):
            pass

        else:
            b.append(a[i+1])
            cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import bisect

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

minimum = A[0]
ans = 1
for a in A[1:]:
    if minimum > a:
        minimum = a
        ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
N=list(map(int, input().split()))
N=N[0]
A=[]
previous=-1
color=0
for i in range(N):
    I=int(input())
    if I==previous:
        color+=1
    else:
        A.append(I)
        previous=I
    

while len(A)>0:
    color+=1
    max=-1
    sub=[]
    for i in A:
        if i>max:
            max=i
        else:
            sub.append(i)
    A=sub
    
print(color)

Submission status: Wrong Answer

Solution code:
class heaptree():
    L=[None]
    N=0
    def __init__(self):
        self.L=[None]
        self.N=0
    def debug(self):
        return self.L
    def heappush(self,v):
        self.L.append(v)
        self.N+=1
        i=self.N
        while(i>1):
            if self.L[i//2]<self.L[i]:
                self.L[i//2],self.L[i]=self.L[i],self.L[i//2]
                i=i//2
            else:
                break
    def value(self):
        if self.N==0:
            return None
        else:
            return self.L[1]
    def heappop(self):
        if self.value()==None:
            return None
        res=self.L[1]
        self.L[1]=self.L[-1]
        self.L.pop()
        self.N-=1
        i=1
        while(i<=self.N):
            if 2*i+1<=self.N:
                if self.L[i]>self.L[2*i] and self.L[i]>self.L[2*i+1]:
                    break
                elif self.L[2*i]<self.L[2*i+1]:
                    self.L[i],self.L[2*i+1]=self.L[2*i+1],self.L[i]
                    i=2*i+1
                else:
                    self.L[i],self.L[2*i]=self.L[2*i],self.L[i]
                    i=2*i
            elif 2*i==self.N:
                if self.L[i]>self.L[2*i]:
                    break
                else:
                    self.L[i],self.L[2*i]=self.L[2*i],self.L[i]
                    i=2*i
            else:
                break
        return res
N=int(input())
a=[int(input()) for i in range(N)]
Q=heaptree()
Q.heappush(a[0])
for i in range(1,N):
    if a[i]<=Q.value():
        Q.heappush(a[i])
print(Q.N)

Submission status: Wrong Answer

Solution code:
inf = float('inf')

class SegmentTree:

    def __init__(self,arr):
        self.n = pow(2,(len(arr)-1).bit_length())
        self.nodes = [inf]*(2*self.n-1)
        for i in range(len(arr)):
            self.nodes[self.n-1+i] = arr[i]
        for i in range(self.n-1)[::-1]:
            self.nodes[i] = min(self.nodes[2*i+1],self.nodes[2*i+2])

    def query(self,l,r):
        l += self.n - 1; r += self.n - 1
        res = inf
        while l < r:
            if r & 1:
                r -= 1
                res = min(res, self.nodes[r-1])
            if l & 1:
                res = min(res, self.nodes[l-1])
                l += 1
            l >>= 1; r >>= 1
        return res

    def update(self,i,x):
        i += self.n - 1
        self.nodes[i] = x
        while i > 0:
            i = (i-1)//2
            self.nodes[i] = min(self.nodes[2*i+1],self.nodes[2*i+2])

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

ans = 0
st = SegmentTree([inf]*N)
for i,a in enumerate(A):
    if a <= st.query(0,i):
        ans += 1
    st.update(i,a)

print(ans)

Submission status: Wrong Answer

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

c = []
for i in range(N):
    n = int(input())
    index = bisect.bisect_left(c,n)
    if index == 0:
        c.append(n)
    else:
        c[index-1] = n
    #print(c)

print(len(c))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
for i in range(n):
  a.append(int(input()) * 10 ** 5 - i)
b = sorted(a)
count = 0
import random
while True:
  now = a[count]
  count += 1
  head = 0
  back = len(b)
  j = 0
  while b[j] != now and back - head != 1:
    if b[j] == now:
      break
    elif b[j] > now:
      back = j
    else:
      head = j
    j = random.randrange(head,back)
  b = b[:j]
  if b == []:
    break
print(count)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

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

print(len(LIS))

Submission status: Wrong Answer

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

A = sorted(A, key=lambda x: (x[1], -1 * x[0]))
# print(A)

import heapq
memo = [100000000000000]
for a in A:
    num = a[0]
    smallest = heapq.heappop(memo)
    # print(smallest, num)
    if num < smallest:
        heapq.heappush(memo, num)
        heapq.heappush(memo, smallest)
    else:
        heapq.heappush(memo, num)

print(len(memo) - 1)

Submission status: Wrong Answer

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

color_count = 0
num_prev = 10e10
color_list = []

for num in number_list:
	if num < num_prev:
		if color_list == []:
			color_count +=1
			color_list.append(num)
		else:
			same_color = False
			for idx, c_num in enumerate(color_list[::-1]):
				if c_num < num:
					color_list[-idx-1] = num      
					same_color = True
					break
          
			if not same_color:
				color_count +=1
				color_list.append(num)
	else:
		color_list[-1] = num
	num_prev = num

print(color_count)

Submission status: Wrong Answer

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

B = [[A[0]]]
for n in range(N-1):
  if A[n] < A[n+1]:
    B[-1].append(A[n+1])
  else:
    B.append([A[n+1]])

C = [B[0]]
for n in range(1, len(B)):
  for m in range(1, len(C)):
    if C[-m][-1] < B[n][0]:
      C[-m] += B[n]
      break
  else:
    C.append(B[n])

ans = len(C)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
a = [0] * n

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

color = [a[0]]
color_min = a[0]

for i in range(1, n):
    if color_min >= a[i]:
        bisect.insort_left(color, a[i])
        color_min = a[i]
    else:
        j = bisect.bisect_left(color, a[i])
        color.pop(j-1)
        bisect.insort_left(color, a[i])


print(len(color))

Submission status: Wrong Answer

Solution code:
import bisect

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

ans = [A[0]]
l = 1

for i in range(1, N):
    n = bisect.bisect_right(ans, A[i])
    if n == 0:
        ans = [A[i]] + ans
        l += 1
    elif n >= l:
        if ans[n - 1] == A[i]:
            ans = ans[:n] + [A[i]] + ans[n:]
        else:
            ans[n - 1] = A[i]
    else:
        if ans[n] == A[i]:
            ans = ans[:n] + [A[i]] + ans[n:]
        else:
            ans[n] = A[i]

print(len(ans))

Submission status: Wrong Answer

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

answer = 0

for i in A:
  group = [i]
  for j in A[i:]:
    if i < j:
      group.append(j)
      A.remove(j)
  if len(group) > 0:
    answer += 1
  if len(A) == 0:
    break


print(answer)