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:
import bisect
n=int(input())
a=[int(input()) for i in range(n)]
inf=10**6
tmp=[inf]*n
ans=0
for i in range(n-1,-1,-1):
  j= bisect.bisect_right(tmp,a[i])
  tmp[j]=a[i]
for i in range(n):
  if tmp[i]!=inf:
    ans+=1
print(ans)

Submission status: Runtime Error

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 l[i] >= l[i+1]:
        cnt += 1
    else:
        cnt = 0
    if L <= cnt:
        L = cnt
print(L)

Submission status: Runtime Error

Solution code:
import sys

def saiki(i,count,arr,end):
  count += 1
  tmp = arr[i]
  end[i] = True
  for j in range(i+1,len(arr)):
    if end[j]:
      continue
    if tmp < arr[j]:
      end[j] = True
      continue
      tmp = arr[j]
    count = saiki(j,count,arr,end)
  
  return count

def main():
  n = int(input())
  a = []
  last_num = -1
  count = 0
  for i in range(n):
    a.append(int(input()))
  end = [False] * n
  
  count = saiki(0,count,a,end)
  
  print(count)

main()

Submission status: Runtime Error

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


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

Solution code:
import bisect
n=int(input())
a=[int(input()) for i in range(n)]
inf=10**6
tmp=[inf]*(n+1)
ans=0
for i in range(n-1,-1,-1):
  j= bisect.bisect_right(tmp,a[i])
  tmp[j]=a[i]
for i in range(n):
  if tmp[i]!=inf:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
n=int(input())
a=[int(input()) for i in range(n)]
inf=10**6
tmp=[inf]*(n+1)
ans=0
for i in range(n-1,-1,-1):
  j= bisect.bisect_right(tmp,a[i])
  tmp[j]=a[i]
for i in range(n):
  if tmp[i]!=inf:
    ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[0]*n
min=[0]*0
max=[0]*0
for i in range(n):
    a[i]=int(input())
    if(i==0):
        min.append(a[0])
        continue
    if(a[i-1]>=a[i]):
        max.append(a[i-1])
        min.append(a[i])
        if(i==n-1):
            max.append(a[i])
    
#print(a)
#print(min)
#print(max)

for _ in range(1):
    for i in range(len(max)):
      owari=False
      for j in range(i):
         if(max[j]<min[i]):
                max[j]=max[i]
                #max.pop(i)
                #min.pop(i)
                min[i]=-1
                owari=True
                break
    if(owari):break

#print(min)
#print(max)

ans=0
for i in range(len(min)):
    if(min[i]!=-1):
        ans+=1

print(ans)

Submission status: Runtime Error

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]])#常に小さい順にソートされている
color = 1
for n,a in enumerate(A):
    if n==0:
        continue
    else:
        pos = bisect.bisect_left(surface,a) -1 #a未満の最大の整数
        if pos==0:
            color += 1
            surface.appendleft(a)
        else:
            surface[pos-1] = a
print(color)

Submission status: Runtime Error

Solution code:
import collections
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))
mi = 10000000000000
res = collections.deque([])
res.append(dat[0])
import bisect
for i in range(1, n):
    a = bisect.bisect_left(res, dat[i])
    if a == 0:
        bisect.insort_left(res, dat[i])
    else:
        res[a-1] = dat[i]
print(len(res))

Submission status: Runtime Error

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

count = 1
def f(list):
    lt = []
    mt = []
    for j in range(0,len(list)):
        if list[j] > list[-1] or j == len(list)-1:
            mt.append(list[j])
        else:
            lt.append(list[j])
    if (len(lt)>0 and len(mt)>0):
        return f(lt)+f(mt)
    else:
        return 1
print(f(a))

Submission status: Runtime Error

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 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未満の最大の整数
        if pos==0:
            surfMin = a
        else:
        surface[pos-1] = a
print(color)

Submission status: Runtime Error

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 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-1] = a
        if pos==0:
            surfMin = a
print(color)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import heapq


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    heapq.heappush(heads, -a)
    while A:
        a = A.pop()
        h = -heapq.heappop(heads)
        if a < h:
            for b in heads[::-1]:
                if - b > a:
                    heads.remove(b)
                    heapq.heapify(heads)
                    heapq.heappush(heads, -a)
                    break
        else:
            heapq.heappush(heads, -a)
            heapq.heappush(heads, -h)
    return len(heads)
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
import copy
import numpy as np
b = copy.copy(a)
a = np.array(a)
b = np.array(b)
min_i = a.argmin()
min_v = a.min()

nn = copy.copy(n)
cnt = 1
res = 0
while len(b) > 0:
    for i in range(nn-min_i-1):
        if min_v >= b[min_i + cnt]:
            b = np.delete(b, np.s_[min_i:min_i + i +2])
            res += 1
            break
        if min_i + i +1 == nn-min_i:
            b = np.delete(b, np.s_[min_i:min_i + i +2])
            res += 1
#     print(b)
    min_i = b.argmin()
    min_v = b.min()
    nn = len(b)
#     print(min_i)
#     print(min_v)
    if len(b) == 1:
        res += 1
        break
print(res)

Submission status: Runtime Error

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]

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

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

print(num_color)
exit(0)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
import copy
import numpy as np
b = copy.copy(a)
a = np.array(a)
b = np.array(b)
min_i = a.argmin()
min_v = a.min()
cnt = 1
nn = copy.copy(n)cnt = 1
res = 0
while len(b) > 0:
    for i in range(nn-min_i-1):
        if min_v >= b[min_i + cnt]:
            b = np.delete(b, np.s_[min_i:min_i + i +2])
            res += 1
            break
        if min_i + i +1 == nn-min_i:
            b = np.delete(b, np.s_[min_i:min_i + i +2])
            res += 1
#     print(b)
    min_i = b.argmin()
    min_v = b.min()
    nn = len(b)
#     print(min_i)
#     print(min_v)
    if len(b) == 1:
        res += 1
        break
print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import heapq


def solve():
    N = int(input())
    A = []
    heads = []
    for _ in range(N):
        A.append(int(input()))
    a = A.pop()
    heapq.heappush(heads, -a)
    while A:
        a = A.pop()
        h = -heapq.heappop(heads)
        if a < h:
            for b in heads[::-1]:
                if - b > a:
                    heads.remove(b)
                    heapq.heappush(heads, -a)
                    break
        else:
            heapq.heappush(heads, -a)
            heapq.heappush(heads, -h)
    return len(heads)
  

def main():
    print(solve())


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(input()) for i in range(n)]
import copy
import numpy as np
b = copy.copy(a)
a = np.array(a)
b = np.array(b)
min_i = a.argmin()
min_v = a.min()
cnt = 1
nn = copy.copy(n)cnt = 1
res = 0
while len(b) > 0:
    for i in range(nn-min_i-1):
        if min_v >= b[min_i + cnt]:
            b = np.delete(b, np.s_[min_i:min_i + i +2])
            res += 1
            break
        if min_i + i +1 == nn-min_i:
            b = np.delete(b, np.s_[min_i:min_i + i +2])
            res += 1
#     print(b)
    min_i = b.argmin()
    min_v = b.min()
    nn = len(b)
#     print(min_i)
#     print(min_v)
    if len(b) == 1:
        res += 1
        break

Submission status: Runtime Error

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])
if a[0][1] == 0:
	co += 1
for i in range(1,len(aa)):
	for j in range(len(d)):
		if d[j] < a[i] and (d[j] < a[i] or a[i] == 0):
			d.popleft()
			d.append(a[i])
			break
	else:
		co += 1
		d.append(a[i])
print(co)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[0]*n
min=[0]*0
max=[0]*0
for i in range(n):
    a[i]=int(input())
    if(i==0):
        min.append(a[0])
        continue
    if(a[i-1]>=a[i]):
        max.append(a[i-1])
        min.append(a[i])
        if(i==n-1):
            max.append(a[i])
    
#print(a)
#print(min)
#print(max)

for _ in range(1):
    for i in range(len(max)):
      owari=False
      for j in range(i):
         if(max[j]<min[i]):
                max[j]=max[i]
                #max.pop(i)
                #min.pop(i)
                min[i]=-1
                #owari=True
                break
    if(owari):break

#print(min)
#print(max)
print(len(max))

Submission status: Runtime Error

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

AA=[]
for i in range(n):
    AA.append([A[i],i])

A = AA[:]
A.sort(key=lambda x:x[0])

mm = 10**5+10
B=[0 for i in range(mm)]
for i in range(n):
    if A[i]<=mm:
        B[A[i]]+=1
        mm=A[i]
    else:
        t=A[i]
        while B[t]==0:
            t-=1
        B[t]-=1
        B[A[i]]+=1
        #print(B)
        if mm==t and B[t]==0:
            while B[mm]==0:
                mm+=1
print(sum(B))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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


# N = 2*10**3
# A = [0 for n in range(N)]

# print(A)

visited = [False for n in range(N)]

dp = {}
def search(n,d):
    if n in dp:
        return dp[n]
    maxd = d
    for i in range(n)[::-1]:
        if i in dp:
            maxd = max(dp[i], maxd)
        elif A[i] >= A[n]:
            maxd = max(search(i,d+1), maxd)
    dp[n] = maxd
    return dp[n]

ds = [0 for n in range(N)]
for n in range(N)[::-1]:
    if not n in dp:
        ds[n] = search(n,0)

# print(ds)

print(max(ds)+1)

Submission status: Runtime Error

Solution code:
N=int(input())
A=[0]*N
maxA=[-1]*N
cnt=0
for i in range(N):
  A[i]=int(input())
  for k in range(N):
    if maxA[k]<A[i]:
      if maxa[k]==-1:
        cnt+=1
      maxA[k]=A[i]
      break
print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())

A = []

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

color = 1

def hantei(start):
    global color
    current = start - 1

    while current >= 0:
        if A[current] >= A[start]:
            color += 1
            hantei(current)
            return
        else:
            current -= 1
            start -= 1

hantei(N-1)

print(color)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
a_list = []
for i in range(N):
    a_list.append(int(input()))
color_counter = 0
for i in range(N):
    color_counter += 1
    compare_a = a_list[0]
    next_a_list = []
    for i in range(N):
        if compare_a < a_list[i]:
            compare_a = a_list[i]
        else:
            next_a_list.append(a_list[i])
    if len(next_a_list) == 0:
        break
    else:
        a_list = next_a_list
print(color_counter)

Submission status: Runtime Error

Solution code:
N = int(input())
from collections import deque
l = []
for i in range(N):
    l.append(int(input()))
cnt = 0
while len(l) > 0:
    smallest = min(l)
    ind = l.index(smallest)
    small = l.pop(ind)
    memo = []
    for i in range(ind,len(l)):
        if l(i) > small:
            memo.append(l(i))
            small = l(i)
    for i in range(len(memo)):
        l.pop(l.index(memo(i)))
    cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import copy


def solve(N: int, A: "List[int]"):
    num = 0
    Acopy = [[n, True] for n in A]
    ans = 0
    flag = True

    while(flag):
        ans += 1
        min = 0

        flag = False
        for a in Acopy:
            if a[1]:
                if a[0] > min:
                    min = a
                    a[1] = False
                flag = True

    print(ans)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
ls = [0]*n + [n+1]
for i in range(n-1,-1,-1):
    m = int(input())
    index = bisect.bisect_left(ls,m)
    print(index,0)
    ls[index] = m
conte = 0
for i in range(n-1,-1,-1):
    if ls[i] != 0:
        conte += 1
print(conte-1)
print(ls)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
ans = 0
total = 0
while sum(A) != len(A)*(-1):
    m = max(A)
    ans += 1
    compare = -1
    for i,a in enumerate(A[total:]):
        if a != -1:
            if a > compare:
                compare = a
                A[i+total] = -1
                total += 1
        if a == m:
            break
print(ans)

Submission status: Runtime Error

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

Solution code:
N = int(input())
nums = [int(input()) for _ in range(N)]
ans = 0
nums_sorted = nums[:]
nums_sorted = list(set(nums_sorted))
nums_sorted.sort(reverse=True)
di = {}





for i in range(N-1):
    if nums[i] > nums[i+1]:
        ans += 1

nums_l = len(nums)
nums_s = len(list(set(nums)) )
ans += nums_l - nums_s
if len(nums_s) == 1:
    ans += 1



print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""

# i が与えられたとき a1~aiまでの和を計算する( O(log n) )
def bitsum(bit,i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i&(-i)
    return s
    
# i と x が与えられたとき ai += x とする ( O(log n) )
def bitadd(bit,i,x):
    while i <= n:
        bit[i] += x
        i += i&(-i)
    return bit
    

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

def main():
    nmin = 10**9
    cnt = 0
    
    #bitの構築
    n_ = int(math.log2(N)) + 1
    bit = [0] * (2**n_)
    bit.insert(0,0)
    for n in range(N):
        cnt = n - bitsum(bit, A[n])
        bitadd(bit,n+1,A[n])
    
    print(abs(cnt+1))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
ans = 0
total = 0
while sum(A) != len(A)*(-1):
    m = max(A)
    ans += 1
    compare = -1
    for i,a in enumerate(A[total:]):
        
        if a != -1:
            if a > compare:
                compare = a
                A[i+total] = -1
                total += 1
        if a == m:
            break
        print(A)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
from collections import deque
l = deque()
for i in range(N):
    l.append(int(input()))
cnt = 0
while len(l) > 0:
    smallest = min(l)
    ind = l.index(smallest)
    small = l.pop(ind)
    memo = []
    for i in range(ind,len(l)):
        if l(i) > small:
            memo.append(l(i))
            small = l(i)
    for i in range(len(memo)):
        l.pop(l.index(memo(i)))
    cnt += 1
print(cnt)

Submission status: Runtime Error

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+1)

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

Solution code:
import sys

n= int(sys.stdin.readline())
ai= [ int(sys.stdin.readline()) for _ in range(n) ]
c= 1
l= [ -1 ]
for i in range(n-1):
    a = ai[i]
    k= -1
    for j in range(c):
        if l[j]<a:
            k= j
            break
    #
    if k>=0:
        l[k]= ai[i]
    else:
        c+=1
        l.append(None)
#
print( c )

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:
from bisect import bisect_left
N, *A = map(int, open(0).read().split())

INF = 10 ** 6
dp = [INF] * (N + 1)
ans = 0
for i in range(N):
    idx = bisect_left(dp, A[i])
    dp[idx] = A[i]
    ans += 1 if idx == 0 else 0
print(ans)

Submission status: Runtime Error

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

def aa(li):
    max_val = max(li)
    a = [i for i, x in enumerate(li) if x == max(li)]    
    b = max(a)
    return max_val, b

cnt = 0

tmp = N

while True:
    ans = []
    while True:
        mv, tmp = aa(li[:tmp])
        ans.append(tmp)
        cnt += 1
        if tmp == 0:
            break
    
    for i in ans:
        li.pop(i)
    if len(li) == 0:
        break

print(cnt)

Submission status: Runtime Error

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)-1):
  for m in range(1, len(C)):
    if C[-m][-1] < B[n][0]:
      C[-m].append(B[n])
      break
  else:
    C.append([B[n]])

ans = len(C)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

INF = float("inf")


def solve(N: int, A: "List[int]"):

    a = deque([-INF])

    def isOK(index, key):
        return a[index] < key

    def binary_search(key):
        ng = -1
        ok = len(a)

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok

    ans = 0
    for aval in A:
        ok = binary_search(aval)
        # print(a, a[ok])
        if a[ok] == -INF:
            ans += 1
        a.insert(ok, aval)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(4100000)

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)


def resolve():
    N = [int(x) for x in sys.stdin.readline().split()][0]
    a_list = [[int(x) for x in sys.stdin.readline().split()][0]
              for _ in range(N)]

    logger.debug('{} {}'.format(N, a_list))

    min_list = [10**10]
    max_min = 10**10
    i_max = 0
    for i, a in enumerate(reversed(a_list)):
        if a >= max_min:
            max_min = a
            min_list.append(a)
            i_max = i
        else:
            min_list[i_max] = a
            max_min = max(min_list)

    print(len(min_list))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
2
1
4
5
3"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
0
0
0
0"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """1
0"""
        output = """1"""
        self.assertIO(input, output)