Problem:


Score : 500 points

Problem Statement

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

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

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

Constraints

1 \leq N \leq 10^5

0 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

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

Sample Input 1

5
2
1
4
5
3

Sample Output 1

2

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

Sample Input 2

4
0
0
0
0

Sample Output 2

4

We have to paint all the integers with distinct colors.



Sample input:
5
2
1
4
5
3


Sample output:
2

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
L = deque([int(input())])
for i in range(1,n):
    t = int(input())
    a = L.popleft()
    if t <= a:
        L.append(t)
        L.append(a)
    else:
        L.append(t)
print(len(L))

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
A = []
count = 0
for _ in range(n):
    a = int(input())
    if len(A) == 0:
        A.append(a)
        count += 1
        continue
    i = bisect.bisect_right(A, a)
    if i == 0:
        A.insert(0, a)
        count += 1
    else:
        bisect.insort_right(A, a)
        if A[i-1] != A[i]:
            del A[i-1]
        else:
            count += 1

ans = count
print(ans)

Submission status: Wrong Answer

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

ans = 0
b = float('inf')
for a in A:
  if a <= b:
    b = a
    ans += 1
print(ans)

Submission status: Wrong Answer

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

ans = 0
b = float('inf')
for a in A:
  if a < b:
    b = a
    ans += 1
print(ans)

Submission status: Wrong Answer

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

maxa = A[-1]
ans = 0
for a in A[::-1]:
  if a >= maxa:
    ans += 1
    maxa = a
print(ans)

Submission status: Wrong Answer

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

mina = A[-1]
ans = 0
for a in A[::-1]:
  if a <= mina:
    ans += 1
    mina = a
print(ans)

Submission status: Wrong Answer

Solution code:
# E
n = int(input())
import heapq
import bisect
first = int(input())
a = [first]
heapq.heapify(a)   # ヒープ化

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

Submission status: Wrong Answer

Solution code:
# E
n = int(input())
import heapq
import bisect
a = [-1]
heapq.heapify(a)   # ヒープ化
ans = 1

for i in range(n):
    num = int(input())
    cahnge_f = False
    
    if num <= a[0]:
        heapq.heappush(a, num)
    else:
        ind = bisect.bisect_left(a, num)
        ind-=1
        a[ind]=num

print(len(a))

Submission status: Wrong Answer

Solution code:
# E
#しゃくとり方 (ex. 単調増加部分列の長さの最大値)
n=int(input())
a = [int(input()) for i in range(n)]

count=0
right=0
for left in range(n):
    if left==right: right+=1
    while right<n and a[right-1] >= a[right]:
        right+=1
    count=max(count,right-left)
print(count)

Submission status: Wrong Answer

Solution code:
# E
n = int(input())
import heapq
a = [-1]
heapq.heapify(a)   # ヒープ化
ans = 1

for i in range(n):
    num = int(input())
    cahnge_f = False
    for j in range(ans-1,-1,-1):
        if num > a[j]:
            a.pop(j)
            heapq.heappush(a, num)
            cahnge_f = True
            break
    if not cahnge_f:
        heapq.heappush(a, num)
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from collections import deque
n = int(input())
l = deque([])
l.append(int(input()))
for i in range(n-1):
    a = int(input())
    if l[0] >= a:
        l.appendleft(a)
    else:
        l[bisect.bisect_right(l,a)-1] = a
print(len(l))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
l = []
l.append(int(input()))
for i in range(n-1):
    a = int(input())
    if l[0] >= a:
        l.insert(0,a)
    else:
        l[bisect.bisect_left(l,a+1)-1] = a
print(l)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int, read().split()))
#print(a)

import heapq
c = [-10**9+10]
heapq.heapify(c)

for ai in reversed(a):
    ci = heapq.heappop(c)
    if -ai > ci:
        heapq.heappush(c, -ai)
    else:
        heapq.heappush(c, -ai)
        heapq.heappush(c, ci)
    #print(ai, ci, c)
print(len(c))

Submission status: Wrong Answer

Solution code:
import bisect

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right,insort_right
N = int(input())
A = [int(input()) for _ in range(N)]
G = []
for i in range(N):
    a = A[i]
    ind = bisect_right(G,a)
    if ind==0:
        insort_right(G,a)
    else:
        if G[ind-1]<a:
            G[ind-1] = a
        else:
            insort_right(G,a)
print(len(G))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def JOI14_B():
    N = I()
    A = [I()for _ in range(N)]
    A.extend(A)
    dp = [[0]*(N*2+1) for _ in range(N*2+1)]

    for j in range(N):
        for i in range(N*2-j):
            if (N-j)%2==1:
                dp[i][i+j] = max(dp[i+1][i+j]+A[i],dp[i][i+j-1]+A[i+j])
            else:
                if A[i]>A[i+j]:
                    dp[i][i+j] = dp[i+1][i+j]
                else:
                    dp[i][i+j] = dp[i][i+j-1]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i+N-1])
    print(ans)
    #print(dp)
    return

def square869120Contest1_G():
    def held_karp(dists,TL):
        # Copyright (c) 2016 Carl Ekerot
        """
        Implementation of Held-Karp, an algorithm that solves the Traveling
        Salesman Problem using dynamic programming with memoization.
        Parameters:
            dists: distance matrix
        Returns:
            A tuple, (cost, path).
        """
        n = len(dists)

        # Maps each subset of the nodes to the cost to reach that subset, as well
        # as what node it passed before reaching this subset.
        # Node subsets are represented as set bits.
        C = {}
        dp = defaultdict(int)

        # Set transition cost from initial state
        for k in range(1, n):
            C[(1 << k, k)] = (dists[0][k], 0)
            dp[(1 << k, k)] = 1

        # Iterate subsets of increasing length and store intermediate results
        # in classic dynamic programming manner
        for subset_size in range(2, n):
            for subset in itertools.combinations(range(1, n), subset_size):
                # Set bits for all nodes in this subset
                bits = 0
                for bit in subset:
                    bits |= 1 << bit
                shortest_length = inf
                # Find the lowest cost to get to this subset
                for k in subset:
                    prev = bits & ~(1 << k)

                    res = []
                    for m in subset:
                        if not (prev, m) in C:
                            continue
                        if m == 0 or m == k:
                            continue
                        if C[(prev, m)][0] + dists[m][k]>TL[m][k]:
                            continue
                        res.append((C[(prev, m)][0] + dists[m][k], m))
                        if shortest_length>C[(prev, m)][0] + dists[m][k]:
                            shortest_length = C[(prev, m)][0] + dists[m][k]
                    if not res:
                        continue
                    C[(bits, k)] = min(res)
                    for d,m in res:
                        if shortest_length!=d:
                            continue
                        dp[(bits, k)] += dp[(prev,m)]

        # We're interested in all bits but the least significant (the start state)
        bits = (2 ** n - 1) - 1

        # Calculate optimal cost
        res = []
        shortest_length = inf
        for k in range(1, n):
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            res.append((C[(bits, k)][0] + dists[k][0], k))
            if shortest_length > C[(bits, k)][0] + dists[k][0]:
                shortest_length = C[(bits, k)][0] + dists[k][0]
        if not res:
            return False
        opt, parent = min(res)
        way = 0
        for d, k in res:
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            if shortest_length < d:
                continue
            way += dp[(bits,k)]

        # Backtrack to find full path
        path = []
        for i in range(n - 1):
            path.append(parent)
            new_bits = bits & ~(1 << parent)
            _, parent = C[(bits, parent)]
            bits = new_bits

        # Add implicit start state
        path.append(0)

        return shortest_length, list(reversed(path)), way

    N, M = LI()
    dist = [[inf]*N for _ in range(N)]
    TL = [[0]*N for _ in range(N)]
    for _ in range(M):
        s, t, d, time = LI()
        s -= 1; t -= 1
        dist[s][t] = dist[t][s] = d
        TL[s][t] = TL[t][s] = time
    ans = held_karp(dist,TL)
    if (not ans) or ans[2]==0:
        print("IMPOSSIBLE")
        return
    print(ans[0],ans[2])
    return

def JOI13_D():
    def solve(yday,leader,next):
        a = [0]*3
        for i in range(3):
            if next&(1<<i)==(1<<i):
                a[i] = 1
        rep = 0
        if a[leader]==0:
            return rep
        for i in range(3):
            if yday&(1<<i)==(1<<i):
                if a[i]==1:
                    rep = 1
        return rep
    N = I()
    S = SI()
    member = {"J":0,"O":1,"I":2}
    dp = [[0]*8 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(N):
        leader = member[S[i]]
        for j in range(8):
            for k in range(8):
                dp[i+1][j] += (dp[i][k]*solve(k,leader,j))
    ans = sum(dp[-1])%10007
    #print(dp)
    print(ans)
    return

def JOI16_D():
    N, M = LI()
    A = [(I()-1)for _ in range(N)]
    imos = [[0] * (N + 1) for _ in range(M)]
    for i in range(M):
        for j in range(N):
            imos[i][j + 1] += imos[i][j] + (A[j] != i)
    cnt = Counter(A)
    dp = [10 ** 9] * (1 << M)
    num = [None] * (1 << M)
    dp[0] = 0
    num[0] = 0
    for b in range(1 << M):
        for i in range(M):
            if b & (1 << i):
                continue
            nb = b | (1 << i)
            if num[nb] is None:
                num[nb] = num[b] + cnt[i]
            l = num[b]
            r = l + cnt[i]
            d = imos[i][r] - imos[i][l]
            dp[nb] = min(dp[nb], dp[b] + d)

    print(dp[-1])
    return

def ABC6_D():
    N = I()
    C = [I() for _ in range(N)]
    LIS = [C[0]]
    for i in range(N):
        if C[i] > LIS[-1]:
            LIS.append(C[i])
        else:
            LIS[bisect.bisect_left(LIS, C[i])] = C[i]
    print(N - len(LIS))
    return

def ABC134_E():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(-A[0])
    L = 1
    for i in range(1,N):
        cur = bisect.bisect_right(que,-A[i])
        #print(que,cur,L)
        if cur>=L:
            que.appendleft(-A[i])
            L += 1
        else:
            que[cur] = -A[i]

    #print(que)
    ans = len(que)
    print(ans)

    return

def JOI7_F():
    n, k = LI()
    for _ in range(k):
        A = LI()

    return

def square869120Contest1_E():
    N, Q = LI()
    A = LI()
    C = LI()
    C.append(1)
    L = [0]*N
    for i in range(1,N):
        L[i] = pow(A[i-1],A[i],mod) + L[i-1]
    #print(L)
    ans = 0
    now = 0
    for i in range(Q+1):
        next = C[i]-1
        cur = abs(L[next]-L[now])
        ans += cur
        ans %= mod
        now = next
        #print(ans)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC134_E()
"""

"""

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect
import sys

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

col = [A.pop()]
col = deque(col)

while A:
    a = A.pop()
    if a <= col[0]:
        col.appendleft(a)
    else:
        x = bisect.bisect_right(col, a)
        col[x - 1] = a

ans = len(col)
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD = 10 ** 9 + 7

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

# 広義単調減少列の長さの最大値を求めれば良い = Aを逆順に見ればLISと同値
# dp[i] := 長さがi以下の部分列で作られる広義単調減少列の最後の要素の最大値
dp = [-1]  # A[i] >= 0 なのでそれ以下の値を設定し、数列の単調性を保つ
for a in reversed(A):
    if dp[-1] <= a:
        dp.append(a)
    else:
        idx = bisect_left(dp, a)
        dp[idx] = a
print(len(dp) - 1)

Submission status: Wrong Answer

Solution code:
import bisect

N=int(input())

line=[]

for _ in range(N):
    A=int(input())
    index=bisect.bisect_left(line,A)
    if index==0:
        line.insert(index,A)
    else:
        line.pop(index-1)
        line.insert(index,A)

print(len(line))

Submission status: Wrong Answer

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LMI(): return list(map(int, input().split()))
MOD = 10 ** 9 + 7

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

# 広義単調減少 (>=) となる区間の大きさの最大値
ans = 0
cnt = 0
for i, a in enumerate(A):
    if i == 0 or A[i - 1] >= a:
        cnt += 1
        ans = max(ans, cnt)
    else:
        cnt = 1
print(ans)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    use = deque([10**6])
    for _ in range(N):
        num = int(input())
        if min(use) >= num:
            use.appendleft(num)
        else:
            index = bisect.bisect_left(use,num)
            use[index-1] = num
    
    print(len(use)-1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

import bisect
from collections import deque
q = deque()

q.append(a[0])

for num in a[1:]:
    if num <= q[0]:
        q.appendleft(num)
    else:
        ind = bisect.bisect_left(q,num)
        if ind==len(q):
            ind-=1
        q[ind]=num

print(len(q))

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
H = []
min_lst = 10 ** 9
for _ in range(N):
    a = int(input())
    if min_lst >= a:
        min_lst = a
        H.append(-a)
    else:
        ind = bisect.bisect_left(H, -a)
        H[ind] = -a
        if ind == len(H) - 1:
            min_lst = a
print(len(H))

Submission status: Wrong Answer

Solution code:
import heapq, bisect

N = int(input())
H = []
min_lst = 10 ** 9
for _ in range(N):
    a = int(input())
    if min_lst >= a:
        min_lst = a
        heapq.heappush(H, -a)
    else:
        H[bisect.bisect_left(H, -a)] = a
print(len(H))

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    n = int(input())
    ans = 0
    b = 10**9 + 1
    for _ in range(n):
        a = int(input())
        if b >= a:
            b = a
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    n = int(input())
    buf = []
    a = [None] * n
    for i in range(n):
        a[i] = int(input())
    for i in reversed(a):
        index = bisect.bisect_left(buf, i)
        if index < len(buf) and buf[index] > i:
            buf[index] = i
        else:
            buf.append(i)
    print(len(buf))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect

def main():
    n = int(input())
    a = []
    for _ in range(n):
        target = int(input())
        target = 10**9 + 1 - target 
        index = bisect.bisect_left(a, target)
        if index < len(a) and a[index] > target:
            a[index] = target
        else:
            a.append(target)
    print(len(a))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop
import bisect

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = []
for _ in range(N):
    a = ir()
    i = bisect.bisect_left(A, a)
    if i == 0:
        heappush(A, a)
    else:
        A[i-1] = a

print(len(A))
# 14

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

N = int(input())
d = defaultdict(list)

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

keys = sorted(d.keys())
s = d[keys[0]]

for k in keys[1:]:
    used = set()
    for i in d[k]:
        j = bisect_left(s, i)
        if j!=0:
            if not s[j-1] in used:
                s[j-1] = i
            else:
                s = s[:j] + [i] + s[j:]
        else:
            s = [i]+s
        used |= {i}

print(len(s))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

N = int(input())
d = defaultdict(list)

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

keys = sorted(d.keys())
s = d[keys[0]]

for k in keys[1:]:
    used = set()
    for i in d[k]:
        j = bisect_left(s, i)
        if 0<j<=len(s):
            if not s[j-1] in used:
                s[j-1] = i
            else:
                s = s[:j] + [i] + s[j:]
        elif j==0:
            s = [i]+s      
        used |= {i}

print(len(s))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left

N = int(input())
d = defaultdict(list)

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

keys = sorted(d.keys())
s = d[keys[0]]

for k in keys[1:]:
    used = set()
    for i in d[k]:
        j = bisect_left(s, i)
        if 0<j<len(s):
            if not j-1 in used:
                s[j-1] = i
            else:
                s = s[:j] + [i] + s[j:]
            used |= {j-1}
        elif j==0:
            s = [i]+s
        else:
            s = s+[i]

print(len(s))

Submission status: Wrong Answer

Solution code:
N = int(input())
l = [(i+1, int(input())) for i in range(N)]
l.sort(key=lambda x:(x[1],x[0]))

v = 0
a = 0
for i in range(N-1):
    if l[i][0] >= l[i+1][0] or l[i][1] == l[i+1][1]:
        a += 1
    else:
        a = 0
    v = max(v, a)

print(v+1)

Submission status: Wrong Answer

Solution code:
import bisect


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

  tail = []
  len_tail = 0
  for ai in a:
    idx = bisect.bisect_left(tail, -ai, lo=0, hi=len_tail) 
    if idx == len_tail:
      tail.append(-ai)
      len_tail += 1
    else:
      tail[idx] = - ai

  print(len_tail )


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import bisect


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

  tail = []
  len_tail = 0
  for ai in a:
    print(tail, ai)
    idx = bisect.bisect_left(tail, -ai, lo=0, hi=len_tail) 
    if idx == len_tail:
      tail.append(-ai)
      len_tail += 1
    else:
      tail[idx] = - ai

  print(len_tail )


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:

import bisect

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

tail = []
len_tail = 0
for ai in a:
  print(tail, ai)
  idx = bisect.bisect_left(tail, -ai, lo=0, hi=len_tail) 
  if idx == len_tail:
    tail.append(-ai)
    len_tail += 1
  else:
    tail[idx] = - ai

print(len_tail )

Submission status: Wrong Answer

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

x = []

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = len(x) - 1
        l = 0
        while r - l != 1 and r - l != 0:
            m = (r + l) // 2
            if a > x[m]:
                l = m
            else:
                r = m

        if a > x[r]:
            x[r] = a
        elif a > x[l]:
            x[l] = a
        else:
            x.append(a)

print(len(x))

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

color = []
mi = 0
for i in range(N):
    if i == 0:
        color.append(A[i])
        mi = A[i]
    else:
        if A[i] <= mi:
            color.append(A[i])
            mi = A[i]
        else:
            for j in range(len(color)):
                if A[i] > color[j]:
                    color[j] = A[i]
                    break

print(len(color))

Submission status: Wrong Answer

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

mi = float("inf")
ans = 0
for i in range(N):
    if mi >= A[i]:
        ans += 1
        mi = A[i]

print(ans)

Submission status: Wrong Answer

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

from collections import deque
import bisect

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

print(len(d))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = []
    c = 1
    m = int(input())
    for _ in range(N-1):
        a = int(input())
        if a <= m:
            m = a
            c += 1
    print(c)
main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = []
    c = 1
    m = int(input())
    for _ in range(N-1):
        a = int(input())
        if a < m:
            m = a
            c += 1
    print(c)
main()

Submission status: Wrong Answer

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

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

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]

print(len(LIS) - 1)

Submission status: Wrong Answer

Solution code:
N = int(input())
prev = int(1e10)
cnt = 0
for i in range(N):
  a = int(input())
  if a <= prev:
    prev = a
    cnt += 1
    
print(cnt)

Submission status: Wrong Answer

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

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

print(len(b))

Submission status: Wrong Answer

Solution code:
n=int(input())
saisho=10**10
cnt=0
for i in range(n):
    a=int(input())
    if a <= saisho:
        cnt+=1
        saisho=a
    else:
        saisho=min(saisho,a)
print(cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
saisho=10**10
cnt=0
for i in range(n):
    a=int(input())
    if a <= saisho:
        cnt+=1
    saisho=min(saisho,a)
print(cnt)

Submission status: Wrong Answer

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

D = [1]*(N+1)
D[0] = -10**10
print(D)
for a in A:
    idx = bisect(D, -a)
    D[idx] = min(D[idx], -a)
    print(D)
print(bisect(D, 0)-1)

Submission status: Wrong Answer

Solution code:
import bisect
N = int(input())
seq = [-int(input()) for i in range(N)] 
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:
a = int(input())
l = []
for i in range(a):
	t = int(input())
	l.append(t)
d=[False]*a

#print('Hello World')
#a = 5
#l = [2,1,100000,5,3]
used=[]
res =0
for i in range(a):
	if l[i] !=-1:
		f = l[i]
		#print(1,f)
		L = []
		L.append(f)
		res +=1
		l[i] = -1
		for j in range(i+1,a):
			if f < l[j] and l[j] !=-1:
				f = l[j]
				l[i] = -1
				#print(f)
				
				L.append(f)
		#print(L)
#print(used)
print(res)

Submission status: Wrong Answer

Solution code:
a = int(input())
l = []
for i in range(a):
	t = int(input())
	l.append(t)
d=[False]*a

#print('Hello World')
#a = 5
#l = [2,1,100000,5,3]
used=[]
res =0
for i in range(a):
	if l[i] !=-1:
		f = l[i]
		#print(1,f)
		L = []
		L.append(f)
		res +=1
		l[i] = -1
		used.append(f)
		for j in range(i+1,a):
			if f < l[j] and l[j] !=-1:
				f = l[j]
				l[i] = -1
				#print(f)
				
				L.append(f)
				used.append(f)
		#print(L)
#print(used)
print(res)

Submission status: Wrong Answer

Solution code:
a = int(input())
l = []
for i in range(a):
	t = int(input())
	l.append(t)
d=[False]*a

#print('Hello World')
#a = 5
#l = [2,1,100000,5,3]
used=[]
res =0
for i in range(a):
	if l[i] not in used :
		f = l[i]
		#print(1,f)
		L = []
		L.append(f)
		res +=1
		used.append(f)
		for j in range(i+1,a):
			if f < l[j] and l[j] not in used:
				f = l[j]
				#print(f)
				L.append(f)
				used.append(f)
		#print(L)
#print(used)
print(res)

Submission status: Wrong Answer

Solution code:
import sys

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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

import bisect
from collections import deque


def main():
	n=int(input())
	A=[int(input()) for _ in range(n)]
	
	Q=deque([A[0]])
	
	for i in range(1,n):
		if A[i]<=Q[0]:
			Q.appendleft(A[i])

		else:
			ix=bisect.bisect_right(Q,A[i])
			Q[ix-1]=A[i]
	
	print(len(Q))
	
	
	
	
	



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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


#新しい値が最小なら追加，そうでなければそれを超えない最大の値を書き換え
#降順
b=[]
b.append(A[0])


def bi_s(n):
    if b[-1]>=n:
        return -1
    if n>=b[0]:
        return 0
    
    ceil=0
    floor=len(b)-1
    med=1#len(b)==2のとき
    while abs(floor-ceil)>1:
        med=(ceil+floor)//2
        if n>b[med]:
            floor=med
        else:
            ceil=med
    return floor

for i in range(1,N):
    index=bi_s(A[i])
    if index==-1:
        b.append(A[i])
    else:
        b[index]=A[i]
print(len(b))

Submission status: Wrong Answer

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


#新しい値が最小なら追加，そうでなければそれを超えない最大の値を書き換え
#降順
b=[]
b.append(A[0])


def bi_s(n):
    if b[-1]>=n:
        return -1
    if n>=b[0]:
        return 0
    
    ceil=0
    floor=len(b)-1
    med=1
    while abs(floor-ceil)>1:
        med=(ceil+floor)//2
        if n>=b[med]:
            floor=med
        else:
            ceil=med
    return med

for i in range(1,N):
    index=bi_s(A[i])
    if index==-1:
        b.append(A[i])
    else:
        b[index]=A[i]
print(len(b))

Submission status: Wrong Answer

Solution code:
n=int(input())
min=float('inf')
cnt=0
for i in range(n):
    a=int(input())
    if min<a:
        continue
    else:
        min=a
        cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import bisect

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

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)[::-1]
q = deque([])

for i,j in enumerate(a):
  if i == 0:
    q.append(j)
    continue
  c = bisect.bisect_left(q,j)
  if c == 0:
    q.appendleft(j)
  else:
    q[c-1] = j
    
print(len(q))

Submission status: Wrong Answer

Solution code:
import collections
from collections import deque
import bisect

n=int(input())
a=list(int(input()) for i in range(n))
b=deque()
b.append(-1)


for i in range(n):
    if a[i]>b[0]:
        x=bisect.bisect_right(b,a[i])
        b[x-1]=a[i]
    else:
        b.appendleft(a[i])
print(len(b))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpln(n)[::-1]
x = []
heapify(x)
for i,j in enumerate(a):
    if i == 0:
        heappush(x,-j)
        continue
    c = bisect.bisect_left(x,-j)
    # print(c)
    if c == 0:
        heappush(x,-j)
    else:
        x[c-1] = -j
    # print(x)
print(len(x))