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:
# https://atcoder.jp/contests/abc134/tasks/abc134_e
import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left
from collections import deque
from array import array


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = array(sorted(ls))  # insertをO(1)にするためにlistの代わりにdequeを用います

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        idx = self.bisect_left(x)
        self.bst.insert(idx, x)
        # insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    # すべてより小さかったら、新しく追加
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        # bstのなかで、aより小さく且つ一番大きい要素をaに書き換えていく
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc134/tasks/abc134_e
import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right, insort_left
from collections import deque


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html


        ls ... 渡す初期配列
        '''
        self.bst = deque(sorted(ls))  # insertをO(1)にするためにlistの代わりにdequeを用います

    def __repr__(self):
        return f'BST:{self.bst}'

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        idx = self.bisect_left(x)
        self.bst.insert(idx, x)
        # insort_left(self.bst, x)

    def pop_left(self):
        x = self.bst[0]
        del self.bst[0]
        return x

    def pop_right(self):
        x = self.bst[-1]
        del self.bst[-1]
        return x

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_right(x) + 1  # xと同じ大きさも削除したいならbisect_left
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


N = read_a_int()
bst = BinarySearchTree([-1])
for n in range(N):
    a = read_a_int()
    # すべてより小さかったら、新しく追加
    if bst.bst[0] >= a:
        bst.insert(a)
    else:
        # bstのなかで、aより小さく且つ一番大きい要素をaに書き換えていく
        idx = bst.bisect_left(a) - 1
        bst.bst[idx] = a

print(len(bst))

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

N, K = map(int, input().split())

dp = [[[0 for _ in range(2610)] for _ in range(51)] for _ in range(51)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(K + 1):
            dp[i + 1][j + 1][k + 2 * j + 2] += dp[i][j][k]
            if j > 0:
                dp[i + 1][j][k + 2 * j] += dp[i][j][k] * j
                dp[i + 1][j][k + 2 * j] += dp[i][j][k] * j

            dp[i + 1][j][k + 2 * j] += dp[i][j][k]

            if j > 0:
                dp[i + 1][j - 1][k + 2 * j - 2] += dp[i][j][k] * j * j


print(dp[N][0][K] % mod)

Submission status: Runtime Error

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(cur,que)
        if cur>=L:
            que.appendleft(-A[i])
        else:
            que[cur] = -A[i]
            L += 1

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

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:
        H[bisect.bisect_left(H, -a)] = -a
print(len(H))

Submission status: Runtime Error

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

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

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

keys = sorted(d.keys())
s = deque(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.appendleft(i)
        used |= {i}

print(len(s))

Submission status: Runtime Error

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_right(LIS, seq[i])] = seq[i]
print(len(LIS))

Submission status: Runtime Error

Solution code:

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

#a = 5
#l = [2,1,4,5,3]
used=[False]*(a+10)
res =0
for i in range(a):
	if not used[i] and i+1<a:
		f = l[i]
		#print(1,f)
		L = []
		L.append(f)
		res +=1
		used[l[i]] = True
		for j in range(i+1,a):
			if f < l[j] and not used[l[j]]:
				f = l[j]
				#print(f)
				L.append(f)
				used[l[j]] = True
		#print(L)
print(res)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N;
  cin>>N;
  vector<Int> A(N);
  cin>>A;

  Int ans = 0;
  multiset<Int> S;
  for(Int i=0;i<N;i++){
    auto it = S.lower_bound(A[i]);
    if(it == S.begin()){
      ans++;
      S.insert(A[i]);
    }
    else{
      --it;
      S.insert(A[i]);
      S.erase(it);
    }
  }
  cout<<ans<<endl;

  return 0;
}

Submission status: Runtime Error

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] = j
    
print(len(q))

Submission status: Runtime Error

Solution code:
n = int(input())
s = str(input())

dp = [[0]*(n+1) for i in range(n+1)]
#dp[n-1][n-1] = 1

for i in reversed(range(n)):
  for j in reversed(range(n)):
    if s[i] == s[j]:
      dp[i][j] = dp[i+1][j+1]+1

#print(dp)

ans = 0
for i in range(n-1):
  for j in range(i, n):
    ans = max(ans, min(dp[i][j], j-i))
    
print(ans)

Submission status: Runtime Error

Solution code:
mport bisect

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

B=[]
for a in A:
  p=bisect.bisect_left(B,a)
  if p==0:
    B.insert(0,a)
  else:
    B[p-1]=a

print(len(B))

Submission status: Runtime Error

Solution code:
import bisect

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

c=0
B=[]
for a in A:
  p=bisect.bisect_left(b,a)
  if p==0:
    B.insert(0,a)
  else:
    B[p-1]=a

print(len(B))

Submission status: Runtime Error

Solution code:
N = int(input())
A = [-1]
import bisect
for i in range(N):
    a = int(input())
    index = bisect.bisect_left(A,x)
    if index >= 1:
        A[index-1] = a
    else:
        A.insert(0,a)
ans = len(A)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

N=int(input())
A=[int(input()) for i in range(N)]
lst=[]
nowN=max(A)+1
i=0
while i<N:
    if nowN>=A[i]:
        nowN=A[i]
        lst.append([A[i]])
    else:
        lst2=[n[-1] for n in lst]
        if min(lst2)<A[i]
            for n in range(len(lst2)):
                if lst2[n]<A[i]:
                    lst[n].append(A[i])
                    break
        else:
            lst.append([A[i]])
    i+=1
print(len(lst))

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
first = []
for a in A:
    i = bisect.bisect_left(first,a)
    if i == 0:
        first.insert(0,i)
    else:
        first[i-1] = a
print(len(first))

Submission status: Runtime Error

Solution code:
import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
ans = int(0)

N = I()
color = []
a = I()
maxcolor =[]
maxcolor.append(a)
lena = 1
for i in range(N-1):
    a = I()
    minmaxcolor = min(maxcolor)
    if a<=minmaxcolor:
        maxcolor.insert(0,a)
#        maxcolor.append(a)
        lena += 1
    else:
        acandi = bisect.bisect_left(maxcolor, a)
        maxcolor[acandi] = a-1
        """
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        
        for _ in range(aupper+1):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2
        """

#print(maxcolor)
ans = len(maxcolor)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
ans = int(0)

N = I()
color = []
a = I()
maxcolor =[]
maxcolor.append(a)
lena = 1
for i in range(N-1):
    a = I()
    minmaxcolor = min(maxcolor)
    if a<=minmaxcolor:
        maxcolor.insert(0,a)
#        maxcolor.append(a)
        lena += 1
    else:
        acandi = bisect.bisect_left(maxcolor, a)
        maxcolor[acandi] = a
        """
        aupper = lena-1
        alower = int(0)
        acandi = aupper//2
        
        for _ in range(aupper+1):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi+1)//2
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2
        """

#print(maxcolor)
ans = len(maxcolor)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N = I()
cou = int(0)
color = []
a = int(input())
maxcolor =[]
maxcolor.append(a)
lena = 1
for i in range(N-1):
    a = int(input())
    if a<=min(maxcolor):
        maxcolor.append(a)
        lena += 1
    else:
        aupper = lena
        alower = int(0)
        acandi = aupper//2
        while (True):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = ((aupper+acandi)//2) + 1
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2


#print(maxcolor)
ans = len(maxcolor)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N = I()
cou = int(0)
color = []
a = int(input())
maxcolor =[]
maxcolor.append(a)

for i in range(N-1):
    a = int(input())
    if a<=min(maxcolor):
        maxcolor.append(a)
    else:
        aupper = len(maxcolor)
        alower = int(0)
        acandi = (aupper+1)//2
        while (True):
            if maxcolor[acandi]>=a:
                alower = acandi
                acandi = (aupper+acandi)//2 + 1
            else:
                if aupper - alower <= 1:
                    maxcolor[acandi] = a
                    break
                else:
                    aupper = acandi
                    acandi = (acandi + alower) // 2


#print(maxcolor)
ans = len(maxcolor)
print(ans)

Submission status: Runtime Error

Solution code:
import bisect

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

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

a.reverse()
cnt = 0
for i in range(1,n):
    if a[i] + cnt == c[i-1]:
        cnt += 1
    a[i] += cnt
        
INF = 10000000000
dp = [INF] * n

for i in range(n):
    t = bisect.bisect_left(dp,a[i])
    if t != n:
        dp[t] = a[i]

print(bisect.bisect_left(dp,INF))

Submission status: Runtime Error

Solution code:
import bisect

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

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

c.reverse()

for i in range(1,n):
    if c[i] == c[i-1]:
        c[i] += 1
        
INF = 100000000
dp = [INF] * n

for i in range(n):
    dp[bisect.bisect_left(dp,c[i])] = c[i]

print(bisect.bisect_left(dp,INF))

Submission status: Runtime Error

Solution code:
import bisect

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

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

INF = 100000000
dp = [INF] * n

for i in range(n):
    dp[bisect.bisect_left(dp,c[i])] = c[i]

print(n - bisect.bisect_left(dp,INF)+1)

Submission status: Runtime Error

Solution code:
import bisect
n=int(input())
h=[]
for i in range(n):
  a=int(input())
  if len(h)==0:
    h.append(-1*a)
  elif (-1)*a>=h[-1]:
    h.append(-1*a)
  else:
    index=bisect.bisect_right(h,-1*a)
    h[index]=-1*a
  print(h)
print(len(h))

Submission status: Runtime Error

Solution code:
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect_left(self, r):
        bit = self.tree

        if r == 0:
            return 0

        l = 1 << (r.bit_length() - 1)
        if r == l:
            l //= 2

        k = l // 2
        while r - l >= 1:
            if bit[r] > bit[l]:
                l += max(1, k)
            else:
                r = l
                l //= 2
            k //= 2

        return r if bit[r] > bit[l] else l


N, *A = map(int, open(0))

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo) + 10
bit = BIT(M)
for b in B:
    i = bit.bisect_left(b - 1)
    if i != 0:
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Submission status: Runtime Error

Solution code:
class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __str__(self):
        return "BIT: [{}]".format(
            ", ".join(str(self.sum(i + 1) - self.sum(i))
                      for i in range(self.size))
        )

    def bisect_left(self, r):
        bit = self.tree

        if r == 0:
            return 0

        l = 1 << (r.bit_length() - 1)
        if r == l:
            l //= 2

        k = l // 2
        while r - l >= 1:
            if bit[r] > bit[l]:
                l += max(1, k)
            else:
                r = l
                l //= 2
            k //= 2

        return r if bit[r] > bit[l] else l


N, *A = map(int, open(0))

memo = {a: i for i, a in enumerate(sorted(set(A)), 1)}
B = [memo[a] for a in A]
M = len(memo)
bit = BIT(M)
for b in B:
    i = bit.bisect_left(b - 1)
    if i != 0:
        bit.add(i, -1)
    bit.add(b, 1)

print(bit.sum(M))

Submission status: Runtime Error

Solution code:
n=int(input())
import bisect as b
n=int(input())
ans=1
clist=[int(input())]
for i in range(n-1):
    next=int(input())
    pos=b.bisect_left(clist,next)
    if pos==0:
        clist=[next]+clist
        ans+=1
    else:
        clist[pos-1]=next
print(ans)

Submission status: Runtime Error

Solution code:
def se(c, x, h, l):
    if h == l:
        return l
    t = (h+l)//2
    if c[t] < x:
        a = se(c,x,h,t)
    else:
        a = se(c,x,t,h)
    return a
        
    
import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
if len(np.unique(a)) == 1:
    print(len(a))
else:
    for i in a[::-1][1:]:
        if max(c) <= i:
            c.append(i)
        else:
            c[se(c,i,len(c),0)] = i
    print(len(c))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
if len(np.unique(a)) == 1:
    print(len(a))
else:
    for i in a[::-1][1:]:
        if max(c) <= i:
            c.append(i)
        else:
            mask = np.array(c) - i > 0
            c[mask][np.argmin(c[mask])] = i
    print(len(c))

Submission status: Runtime Error

Solution code:
n = input()
aa = []
xx = [-input()]
for _ in xrange(n - 1):
    aa.append(-input())
for a in aa:
    if a >= xx[-1]:
        xx.append(a)
    else:
        i = bisect.bisect_right(xx, a)
        if i == len(xx):
          i -= 1
        xx[i] = a
print len(xx)

Submission status: Runtime Error

Solution code:
n = input()
aa = []
xx = [-input()]
for _ in xrange(n - 1):
    aa.append(-input())
for a in aa:
    if a >= xx[-1]:
        xx.append(a)
    else:
        i = bisect.bisect_right(xx, a)
        if i == len(xx):
          i -= 1
          xx[i] = a
print len(xx)

Submission status: Runtime Error

Solution code:
#ttps://atcoder.jp/contests/abc134/submissions/6459172
from bisect import bisect
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1]
for a in A:
    a *= -1
    i = bisect(dp,a)   #既存に-aを挿入した時のindex
    print(dp)
    if i < len(dp):    #挿入位置が長さより小さい時（要はabsが一番小さくない時
        dp[i] = a      #-aにする
    else:
        dp.append(a)    #右端に-aを普通に追加
    print(dp)

print(len(dp))

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)


n = int(input())
A = []
for i in range(n):
  a = int(input())
  A += [a]
count = 0
while len(A) >= 2:
  i,j = shuk(A)
  del A[i:j]
  count += 1
  
print(count)