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: Runtime Error

Solution code:
def shuk(A):
  maxcol = -2
  ans = 1; start = 0
  s = 1; f = A[0]; l = len(A)
  while s < l:
    if A[s] > f:
      ans += 1
    else:
      if maxcol < ans:
        maxcol = ans
        i = start;j = s
    ans = 1
    start = s
    f = A[s]
    s += 1
  return (i,j)

count = 0
while len(A) >= 2:
  i,j = shuk(A)
  del A[i:j]
  count += 1
  
print(count)

Submission status: Runtime Error

Solution code:
import glob
import numpy as np
import collections


# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = 'ABC\\134\\E'

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class E(Common):

    def resolve(self):

        seq_len = int(self.input_data())
        seq = np.zeros(seq_len, dtype=np.int)
        for i in range(seq_len):
            seq[i] = int(self.input_data())

        count = 0

        for i in range(seq_len):
            if seq[i] != 1000000001:
                count += 1
                self.rec(seq, i)

        print(str(count))

    def rec(self, seq, index):

        part = seq[index+1::]
        part = part[part > index]
        seq[index] = 1000000001
        if len(part) > 0:
            next_index = part.argmin() + index + 1
            self.rec(seq, next_index)
        else:
            return


solver = E(REL_PATH)
solver.exec_resolve()

Submission status: Runtime Error

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

dp = [float('inf')]*n
for i in range(n):
    x = bisect.bisect_right(dp,-a[i])
    dp[x] = -a[i]
c = dp.count(float('inf'))
print(n-c)

Submission status: Runtime Error

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


def solve(A):
    if len(A) == 0:
        return
    indexList = []
    last = A[0]
    for i, v in enumerate(A):
        if v > last:
            indexList.append(i)
            last = v
    del A[0]
    for i in indexList:
        del A[i-1]


counter = 0
while len(A) > 0:
    solve(A)
    counter += 1

print(counter)

Submission status: Runtime Error

Solution code:
import bisect

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

c.append(a[0])

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

for i in range(N-1):
  ai = int(input())
  flag = False
  for m in l:
    if max(m) < ai:
      m.append(ai)
      flag = True
      break
  if flag == False:
    l.append([ai])
    
print(len(l))

Submission status: Runtime Error

Solution code:
    N = int(input())
    As = [int(input()) for _ in range(N)]
     
    def chop(As):
        res = []
        minibatch=[As[0]]
        for i in range(len(As)-1):
            if As[i]<As[i+1]:
                minibatch.append(As[i+1])
            else:
                res.append(minibatch)
                minibatch=[As[i+1]]
        if minibatch:
            res.append(minibatch)
        return res
     
    def kakutei(remains):
        deletes = []
        for i in range (1,len(remains)):
            if remains[0][-1]<remains[i][0]:
                remains[0].extend(remains[i])
                deletes.append(i)
        x = remains[0].copy()
        for d in deletes[::-1]:
            del remains[d]
        del remains[0]
        return (x,remains)
     
    chopped = chop(As)
    remains = chopped
    res = []
    while remains:
        x, remains = kakutei(remains)
        res.append(x)
    print(len(res))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#import bisect
def desc_bin(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it reverse-sorted assuming a
    is reverse-sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return lo
N=int(input())
ans=[]
for _ in range(N):
    num=int(input())
    
    index=desc_bin(ans,num)
    if index==len(ans):
        ans.append(num)
    else:
        ans[index]=num
    print(ans)
print(len(ans))

Submission status: Runtime Error

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

  for _ in range(len(A)):
    if l == r:
      return l
    mid = (r - l) // 2
    if A[mid] <= t:
      l = mid + 1
    else:
      r = mid - 1


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

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

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

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

print(len(B))

Submission status: Runtime Error

Solution code:
my_list = [a_1, a_2, a_3, ..., a_n]
minimum_color = 1
color_changed = False
for i in my_list:
  if i < my_list(my_list.index(i)+1):
    color_changed = False
  if i > my_list(my_list.index(i)+1 and color_changed == False:
    minimun_color += 1
    color_changed = True

Submission status: Runtime Error

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

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

q = deque([A[0]])
for i in range(1,N):
    insert_index = bisect_left(q,A[i])
    if insert_index == 0:
        q.insert(0, A[i])
    else:
        q[insert_index-1] = A[i]

print(len(q))

Submission status: Runtime Error

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

ans = 0
for i in range(n):
    if len(A) == 0:
        break
    else:
        ans += 1
        for j in range(len(A)-1):
            a = A[0]
            A.remove(A[0])
            if A[j+1] > a:
                a = A[j+1]
                A.remove(A[j+1])
            else:
                pass
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

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

for i in reversed(a[:-1]):
    idx = bisect.bisect_left(t, i + 1)
    print(i, idx)
    if idx == len(t):
        t.append(i)

    else:
        t[idx] = i
    print(t)

print(len(t))

Submission status: Runtime Error

Solution code:
import bisect

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

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

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

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

print(len(t))

Submission status: Runtime Error

Solution code:
import bisect
from collections import deque

N = int(input())

tops = deque()

for i in range(N):
    a = int(input())
    p = bisect.bisect_left(tops, a)
    
    if p == 0:
        bisect.insort_left(tops, a)
    else:    
        tops[p-1] = a
        
print(len(tops))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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


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

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

print(len(B))

Submission status: Runtime Error

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

for i in range(N-1, -1, -1):
  if i == N-1:
    col_min.append(arr[i])
    c += 1
  else:
    check = 0
    for k, v in enumerate(col_min):
      if v > arr[i]
      	col_min[k] = arr[i]
        check = 1
        break
    if check == 0:
      col_min.append(arr[i])
      c += 1
print(c)

Submission status: Runtime Error

Solution code:
N = int(input())
arr = []
for i in range(N):
  arr.append(int(input()))
c = 0
col_min = []

for i in range(N-1, -1, -1):
  if i == N-1:
    col_min.append(arr[i])
    c += 1
  else:
    check = 0
    for k, v in enumerate(col_min):
      if v > arr[i]
      	col_min[k] = arr[i]
        check = 1
        break
    if check == 0:
      col_min.append(arr[i])
      c += 1
print(c)

Submission status: Runtime Error

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

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

maxims = [A[0]]
ans = 1
minim = A[0]
for a in A[1:]:
    if maxims[-1] < a:
        idx = bisect.bisect(maxims,a)
        maxims[idx] = a
    else:
        maxims.append(a)
        ans += 1
    
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
N = int(input())
A = deque()
for _ in range(N):
    x = int(input())
    i = bisect.bisect_left(A,x)
    j = bisect.bisect_right(A,x)
    if len(A) == 0:
        A.append(x)
    elif i > 0:
        if x <= A[i-1]:
            A.insert(i-1, x)
        else:
            A[i-1] = x
    elif x <= A[i]:
        A.insert(i, x)
    elif x > A[i]:
        A[i] = x

print(len(A))

Submission status: Runtime Error

Solution code:
from collections import deque
import bisect
N = int(input())
A = deque()
for _ in range(N):
    x = int(input())
    i = bisect.bisect_left(A,x)
    j = bisect.bisect_right(A,x)
    if len(A) == 0:
        A.append(x)
    elif i > 0:
        if x <= A[i-1]:
            A.insert(i-1, x)
        else:
            A[i-1] = x
    elif x <= A[i]:
        A.insert(i, x)
    elif x > A[i]:
        A[i] = x

print(len(A))

Submission status: Runtime Error

Solution code:
import collections
import bisect

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

Submission status: Runtime Error

Solution code:
from sys import stdin


def increment_left(li, As):
    while True:
        if As[li] < As[li + 1]:
            li += 1
            continue
        break
    return li


def decrement_right(ri, As):
    while True:
        if As[ri] > As[ri - 1]:
            ri -= 1
            continue
        break
    return ri


def main():
    N = int(stdin.readline().rstrip())
    As = [int(stdin.readline().rstrip()) for x in range(N)]
    result = 0
    li = 0
    ri = N - 1
    while True:
        li = increment_left(li, As)
        ri = decrement_right(ri, As)
        if ri <= li:
            result += 1
            break
        if As[li] < As[ri]:
            result += 1
        else:
            result += 2
        li += 1
        ri -= 1
        if ri == li:
            result += 1
            break
        elif ri < li:
            break
    print(result)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import stdin


def increment_left(li, As):
    while True:
        if As[li] < As[li + 1]:
            li += 1
            continue
        break
    return li


def decrement_right(ri, As):
    while True:
        if As[ri] > As[ri - 1]:
            ri -= 1
            continue
        break
    return ri


def main():
    N = int(stdin.readline().rstrip())
    As = [int(stdin.readline().rstrip()) for x in range(N)]
    result = 0
    li = 0
    ri = N - 1
    while True:
        li = increment_left(li, As)
        ri = decrement_right(ri, As)
        if ri <= li:
            result += 1
            break
        if As[li] < As[ri]:
            result += 1
        else:
            result += 2
        li += 1
        ri -= 1
        if ri <= li:
            break
    print(result)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> li;
    li.push_back(a[0]);
    for (int i = 1; i < n; i++) {
        if (a[i] <= li[li.size()-1]) {
            li.push_back(a[i]);
        } else {
            for (int j = 0; j < li.size(); j++) {
                if (li[j] < a[i]) {
                    li[j] = a[i];
                    break;
                }
            }
        }
    }
    printf("%d\n", li.size());
}

Submission status: Runtime Error

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

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

print(max(a))

Submission status: Runtime Error

Solution code:
import bisect

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

B = [A[0]]
for i in range(1, N):
  print(B)
  if A[i] <= B[0]:
    B.insert(0, A[i])
  else:
    index = bisect.bisect_left(B, A[i]) - 1
    B[index] = A[i]
print(len(B))

Submission status: Runtime Error

Solution code:
N = int(input())
ans = {}
for _ in range(N):
  A = int(input())
  D = 0
  for o,i in enumerate(ans):
    if A>i:
      ans[o] = A
      D = 1
      break
  if D == 0:
    ans.add(A)
  
print(len(ans))

Submission status: Runtime Error

Solution code:
import io
import sys
from math import ceil


def IN_S():
  return input()


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


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


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


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


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


test_str = '''
4
0
0
0
0
'''


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


def A():
  n = IN_I()

  l = [IN_I()]

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

    # print("s:", l)
    # print("num:", num)
    if l[0] >= num:
      l.insert(0, num)
      continue

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

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

    inl = 0
    inr = len(l) - 1
    # print("nuita:", l)
    for j in range(0, len(l)):
      mid = ceil((inr - inl) / 2)
      if mid == inl:
        if l[mid] >= num:
          l.insert(mid, num)
        else:
          l.insert(mid + 1, num)
        break
      elif l[mid] == num:
        l.insert(mid, num)
      elif l[mid] > num:
        inr = mid - 1
      else:
        inl = mid + 1

  # print(l)
  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Runtime Error

Solution code:
import io
import sys
from math import ceil


def IN_S():
  return input()


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


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


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


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


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


test_str = '''
4
0
0
0
0
'''


def MAIN():
  T_IN()
  A()


def A():
  n = IN_I()

  l = [IN_I()]

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

    # print("s:", l)
    # print("num:", num)
    if l[0] >= num:
      l.insert(0, num)
      continue

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

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

    inl = 0
    inr = len(l) - 1
    # print("nuita:", l)
    for j in range(0, len(l)):
      mid = ceil((inr - inl) / 2)
      if mid == inl:
        if l[mid] >= num:
          l.insert(mid, num)
        else:
          l.insert(mid + 1, num)
        break
      elif l[mid] == num:
        l.insert(mid, num)
      elif l[mid] > num:
        inr = mid - 1
      else:
        inl = mid + 1

  # print(l)
  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Runtime Error

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import io
import sys
from math import ceil


def IN_S():
  return input()


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


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


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


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


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


test_str = '''
4
0
0
0
0
'''


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


def A():
  n = IN_I()

  l = [IN_I()]

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

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

    inl = 0
    inr = len(l) - 1
    # 1, 2, 3, 4, 5
    for j in range(0, len(l)):
      mid = (inr - inl) // 2
      if mid == inl:
        l.pop(0)
        break
      elif l[mid] == num:
        inr = mid - 1
      elif l[mid] > num:
        inr = mid
      else:
        inl = mid + 1

    inl = 0
    inr = len(l) - 1
    # print(l)
    for j in range(0, len(l)):
      mid = ceil((inr - inl) / 2)
      if mid == inl:
        if l[mid] >= num:
          l.insert(mid, num)
        else:
          l.insert(mid + 1, num)
        break
      elif l[mid] == num:
        l.insert(mid, num)
      elif l[mid] > num:
        inr = mid - 1
      else:
        inl = mid + 1


  # print(l)
  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Runtime Error

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

def bs(m,s,e,a):
    if a>m[e]:
        return e
    if m[(s+e)//2]>a and m[(s+e)//2-1]<=a:
        return (s+e)/2-1
    if m[(s+e)//2]<=a and m[(s+e)//2+1]>a:
        return (s+e)/2
    if m[(s+e)//2]>a and m[(s+e)//2-1]>a:
        return bs(m,s,(s+e)//2,a)
    if m[(s+e)//2]<a and m[(s+e)//2+1]<a:
        return bs(m,(s+e)//2,a)

for i in range(N):
    A=int(input())
    if A<=m[0]:
        m.insert(0,A)
    else:
        m[bs(m,0,len(m)-1,A)]=A

print(len(m))

Submission status: Runtime Error

Solution code:
lst = []
for A in A_list:
    next = -1
    for l in lst:
        if (l < A):
            next += 1
    if (next == -1):
        tmp = lst
        lst = [A]
        lst.extend(tmp)
    elif (next == len(lst)):
        lst.append(A)
    else:
        lst[next] = A
print(len(lst))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import copy

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

for i in range(N):
	if i == 0:
		output.append(A[i])
        min_val = A[i]
	elif A[i] <= min_val:
		output.append(A[i])
		min_val = A[i]
	else:
		cls = 10000000000000000000000000
		for j in range(len(output)):
			if A[i] - output[j] < cls:
				cls = A[i] - output[j]
				plc = j
		output[j] = A[i]
		
print(len(output))

Submission status: Runtime Error

Solution code:
N = int(input())
memo = 1
ans = []
tmp = int(input())
for i in range(1,N):
    A = int(input())
    if A <= tmp:
        memo += 1
    else:
        ans.append(memo)
        memo = 1
    tmp = A
ans.append(mamo)
print(max(ans))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import io
import sys


def IN_S():
  return input()


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


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


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


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


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


test_str = '''
5
5
4
3
5
2
1
'''


def MAIN():
  T_IN()
  A()


def A():
  n = IN_I()

  l = []
  
  snum = -1
  pnum = -1
  for i in range(0, n):
    num = IN_I()
    # print("num:", num )
    if pnum < num:
      pnum = num
      continue

    # print(l, num)
    for j in range(0, len(l) + 1):
      # print(j, len(l))
      if j == len(l):
        # print("l append", pnum)
        l.append(pnum)
      else:
        if l[j] < snum:
          l[j] = pnum
          print (l[j], pnum)
          break

    # print ("pnum", num)
    snum = pnum = num

  if pnum > -1:
    for j in range(0, len(l) + 1):
      if j == len(l):
        l.append(pnum)
      else:
        if l[j] < snum:
          l[j] = pnum
          break

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()

Submission status: Runtime Error

Solution code:
import bisect as bs
import collections

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

col = collections.deque()
min_ = 10000000000

for a in alist:
    if a <= min_:
        col.appendleft(a)
        min_ = a
    else:
        index = bs.bisect(col, a) - 1
        ind = bs.bisect_left(col, col[index])+1
        col[ind] = a

print(len(col))

Submission status: Runtime Error

Solution code:
import bisect

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

Submission status: Runtime Error

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

for _ in range(N):
    n = int(input())
    index = -1
    while n <= b:
        if -index <= len_:
            index -= 1
            b = li[index]
        else:
            c += 1
            li.append(n)
            len_ += 1
            break
    li[index] = b = n

print(c)

Submission status: Runtime Error

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

import math

if __name__ == '__main__':
    N = int(input())
    colors = [
        10000000000
    ]
    # R = [0 for i in range(N)]
    # M = 0

    for i in range(N-1, -1, -1):
        # print('i={}'.format(i))
        for j in range(len(colors)):
            a = int(input())
            if a < colors[j]:
                colors[j] = a
                break
        else:
            colors.append(
                a
            )

    print(len(colors))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())

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

ans_head=[a_list[-1]]

for i in range(n-2,-1,-1):
  a=a_list[i]
  if a>ans_head[-1]:
    ans_head.append(a)
  else:
    insert_index = bisect.bisect_right(ans_head,a)
    ans_head[insert_index]=a

  #print(ans_head)
print(len(ans_head))

Submission status: Runtime Error

Solution code:
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
res = []
res.append(0 - dat[0])

import bisect

for i in range(1, n):
    print(res)
    a = bisect.bisect_right(res, 0 - dat[i])
    print("a={0}".format(a))

    if a == len(res):
        res.append( (0 - dat[i]) )
    else:
        res[a] = (0 - dat[i])

print(len(res))

Submission status: Runtime Error

Solution code:
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
N = int(input())						# 5

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

from bisect import bisect_right as br

for i in range(1,N):
	a = int(input())
	
	r = br(B,a)
	if r==0 or r==len(B):
		ir(B,a)
	else:
		B[r]=a
		
print( len(B) )

Submission status: Runtime Error

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

count = 0
temp = []
tempin = []
for i in range(N):
  if i in tempin:
    continue
  temp.append(A[i])
  for j in range(i+1, N):
    if j in tempin:
      continue
    elif temp[-1] < A[j]:
      temp.append(A[j])
      tempin.append(j)
  else:
    print(tempin)
    count += 1

print(count)

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())

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

ans_head=[a_list[-1]]

for i in range(n-2,0,-1):
  a=a_list[i]
  if a>ans_head[-1]:
    ans_head.append(a)
  else:
    insert_index = bisect.bisect_right(ans_head,a)
    ans_head[insert_index]=a

  #print(ans_head)
print(len(ans_head))

Submission status: Runtime Error

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

Ans=1
a=A[0]
col=[a]
for i in range(1,N):
    same_color=False
    for j in range(i):
        if col[j]<A[i]:
            col[j]=A[i]
            same_color=True
            break
    if not same_color:
        col.append(A[i])

print(len(col))

Submission status: Runtime Error

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 = 1
    else:
        memo = 1
    tmp = A
	ans = max(ans,memo)
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import *

def f(n):
    r = []
    for _ in range(n):
        a = int(input())
        if not r:
            r.append(a)
            continue
        i = bisect_left(r, a)
        if i:
            r[i]=a
        else:
            r = [a] + r
    print(len(r))

n = int(input())
f(n)

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())

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

ans_head=[99999]

for i in range(n-1,0,-1):
  a=a_list[i]
  if a>ans_head[-1]:
    ans_head.append(a)
  else:
    insert_index = bisect.bisect_right(ans_head,a)
    ans_head[insert_index]=a

  #print(ans_head)
print(len(ans_head))

Submission status: Runtime Error

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)
    print(index-1, ai, color)
    if index > 0:
        color[index -1] = ai
    else:
        color.insert(0, ai)
print(len(color), color)

Submission status: Runtime Error

Solution code:
from bisect import bisect


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    L = [A[0]]
    for a in A[1:]:
        if a <= L[-1]:
            L.append(a)
        else:
            i = bisect(L, a)
            L[i] = a
    print(len(L))

    

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())
ans_head=[-1]

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

for i in range(n):
  a=a_list[i]
  if ans_head[0]>=a:
    ans_head=[a].append(ans_head)
  else:
    insert_index = bisect.bisect_left(ans_head,a)
    ans_head[insert_index-1]=a

  #print(ans_head)
print(len(ans_head))

Submission status: Runtime Error

Solution code:
#include <stdio.h>

int main() {
	int n, a, pos, left, right, mid, ans[100010], size = 1;
	scanf("%d %d", &n, &a);
	ans[0] = a;
	for (int i = 1; i < n; i++) {
		scanf("%d", &a);
		if (ans[size - 1] >= a)
			ans[size++] = a;
		else {
			left = 0;
			right = size - 1;
			while (left <= right) {
				mid = (left + right) / 2;
				if (ans[mid] < a) {
					pos = mid;
					right = mid - 1;
				}
				else
					left = mid + 1;
			}
			ans[pos] = a;
		}
	}
	printf("%d\n", size);
	return 0;
}