CodeEff/ECCO huggingface dataset:
# Original solution
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.buffer.readline
N = int(eval(input()))
e = dd(list)
for i in range(1, N):
  n1 = 10 * i
  n2 = i + 1
  e[i].append((n1 % N, 0))
  e[i].append((n2 % N, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [(0, s)]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      if v in vis: continue
      vis.add(v[1])
      for p in self.e[v[1]]:
        d[p[0]] = min(d[p[0]], d[v[1]] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, (d[p[0]], p[0]))
    return d[t]
d = dijkstra(N, e)
print((d.path(1, 0) + 1))

# Optimized solution
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.buffer.readline
N = int(eval(input()))
e = dd(list)
for i in range(1, N):
  n1 = 10 * i
  n2 = i + 1
  e[i].append((n1 % N, 0))
  e[i].append((n2 % N, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d[t]
d = dijkstra(N, e)
print((d.path(1, 0) + 1))
# Original solution
k = int(eval(input()))
from collections import deque
dic = {1:1}
queue = deque([[1,1]])
while queue:
    v,cost = queue.popleft()
    v_ = (v+1)%k
    if not v_ in dic or cost+1<dic[v_]:
        dic[v_] = cost+1
        queue.appendleft([v_,cost+1])
    v_ = v*10%k
    if not v_ in dic or cost<dic[v_]:
        dic[v_] = cost
        queue.append([v_,cost])

print((dic[0]))

# Optimized solution
from collections import deque
K = int(eval(input()))
d={1:1}
q = deque()
q.append([1,1])

while q:
    a,c = q.popleft()
    a_ = (a*10)%K
    if(a_ not in d or c < d[a_]):
        d[a_]=c
        q.appendleft([a_,c])
    b_ = (a+1)%K
    if(b_ not in d or c < d[b_]):
        d[b_] = c+1
        q.append([b_,c+1])

print((d[0]))
# Original solution
#!/usr/bin/python3
# -*- coding: utf-8 -*-

from queue import *


class Edge(object):
    def __init__(self, dst, len_):
        self.dst = dst
        self.len = len_


MAX_K = int(1e5 + 5)
INF = int(1e9)

K = 0
dis = [INF for i in range(0, MAX_K)]
vis = [False for i in range(0, MAX_K)]
edge = [[] for i in range(0, MAX_K)]
q = Queue()


def add(s, t, d):
    edge[s].append(Edge(t, d))


def build():
    for i in range(1, K):
        add(i, i * 10 % K, 0)
        add(i, (i + 1) % K, 1)


def spfa(s):
    dis[s] = 0
    q.put(s)
    while not q.empty():
        x = q.get()
        vis[x] = False
        for e in edge[x]:
            if dis[e.dst] > dis[x] + e.len:
                dis[e.dst] = dis[x] + e.len
                if not vis[e.dst]:
                    q.put(e.dst)
                    vis[e.dst] = True


if __name__ == "__main__":
    K = int(eval(input()))
    build()
    spfa(1)
    print((dis[0] + 1))


# Optimized solution
#!/usr/bin/python3
# -*- coding: utf-8 -*-

from queue import *


class Edge(object):
    def __init__(self, dst, len_):
        self.dst = dst
        self.len = len_


MAX_K = int(1e5 + 5)
INF = int(1e9)

K = 0
dis = [INF for i in range(0, MAX_K)]
vis = [False for i in range(0, MAX_K)]
edge = [[] for i in range(0, MAX_K)]
q = PriorityQueue()


def add(s, t, d):
    edge[s].append(Edge(t, d))


def build():
    for i in range(1, K):
        add(i, i * 10 % K, 0)
        add(i, (i + 1) % K, 1)


def dij(s):
    dis[s] = 0
    q.put((0, s))
    while not q.empty():
        x = q.get()[1]
        if vis[x]:
            continue
        vis[x] = True
        for e in edge[x]:
            if dis[e.dst] > dis[x] + e.len:
                dis[e.dst] = dis[x] + e.len
                q.put((dis[e.dst], e.dst))


if __name__ == "__main__":
    K = int(eval(input()))
    build()
    dij(1)
    print((dis[0] + 1))
# Original solution
from collections import deque

K = int(eval(input()))
D = [-1]*K
Q = deque()
Q.append([1,0])
while D[0] == -1:
    k,v = Q.popleft()
    D[k] = v
    j = (k*10)%K
    if D[j] == -1:
        Q.appendleft([j,v])
    l = (k+1)%K
    if D[l] == -1:
        Q.append([l,v+1])

print((D[0]+1))

# Optimized solution
from collections import deque

K = int(eval(input()))
D = [9999]*K
D[1] = 1
H = deque()
H.append(1)
while len(H) != 0:
    h = H.pop()
    if D[(h*10)%K] > D[h]:
        D[(h*10)%K] = D[h]
        H.append((h*10)%K)
    if D[(h+1)%K] > D[h] + 1:
        D[(h+1)%K] = D[h] + 1
        H.appendleft((h+1)%K)

print((D[0]))
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    K = I()

    # メソッドのみ版
    def search(s):
        d = collections.defaultdict(lambda: inf)
        q = [(1,s)]
        qi = 0
        v = [False] * (K+1)
        v[s] = True
        while len(q):
            k, u = q[0]
            q = q[1:]
            t = u*10 % K
            while not v[t]:
                if t == 0:
                    return k
                q.insert(0, (k, t))
                v[t] = True
                t = t*10 % K

            i = 1
            t = (u+i) % K
            while not v[t]:
                if t == 0:
                    return k+1
                q.append((k+1, t))
                v[t] = True
                i = i*10 % K
                t = (u+i) % K

    return search(1)

print(main())




# Optimized solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    K = I()

    # メソッドのみ版
    def search(s):
        d = collections.defaultdict(lambda: inf)
        q = [(1,s)]
        d[s] = 1
        qi = 0
        v = [False] * (K+1)
        v[s] = True
        while len(q):
            k, u = heapq.heappop(q)
            if u == 0:
                return k
            t = u*10 % K
            v[u] = True
            while not v[t]:
                if t == 0:
                    return k
                if d[t] > k:
                    heapq.heappush(q, (k, t))
                    d[t] = k
                v[t] = True
                t = t*10 % K

            i = 1
            t = (u+i) % K
            while not v[t] and t != u:
                if d[t] > k+1:
                    heapq.heappush(q, (k+1, t))
                    d[t] = k+1
                    i = i*10 % K
                    t = (u+i) % K
                else:
                    break

    return search(1)

print(main())
# Original solution
import time
n = int(eval(input()))
sTime = time.time()

def sum_digit(n):
    s = 0
    while n>0:
        s += n%10
        n //= 10
    return s


mi = n
t = 0
for i in range(1, 10**n):
    mi = min(mi, sum_digit(n*i))
    t = time.time() - sTime
    if t > 2.7:
        break
        
print(mi)

# Optimized solution
n = int(eval(input()))

while n % 2 == 0:
    n //= 2
while n % 5 == 0:
    n //= 5
if n == 1:
    print((1))
else:
    X = [n for i in range(n)]
    
    j = 1
    s = 1
    post = []
    m = 0
    while True:
        s *= 10
        s %= n
        post.append(s)
        X[s] = min(j, X[s])
        m += 1
        if s == 1:
            break
    ans = 0
    while True:
        if ans > 0:
            break
        pre = post
        post = []
        j += 1
        for p in pre:
            pp = (p + 1) % n
            if pp == 0:
                X[0] = j
                ans = j
                break
            if X[pp] == n:
                for i in range(m):
                    post.append(pp)
                    X[pp] = j
                    pp *= 10
                    pp %= n
    print(ans)
# Original solution
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

k = int(eval(input()))

g = [[] for _ in range(k)]
for i in range(k):
    g[i].append(((i+1)%k,1))
    if i: g[i].append((10*i%k,0))
#print(g)

from collections import deque
q = deque([(1,1)])
res = [float("inf")]*k
res[1] = 1
while q:
    dd,v = q.popleft()
    if res[v] < dd: continue
    if v==0: break
    for c,d in g[v]:
        if res[c] <= res[v] + d: continue
        res[c] = res[v] + d
        if d: q.append((res[c],c))
        else: q.appendleft((res[c],c))

print((res[0]))




# Optimized solution
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

k, = list(map(int, readline().split()))

from collections import deque
INF = 1<<30
res = [INF]*k
res[1] = 1

q = deque([(1,1)])
while q:
    dv,v = q.popleft()
    if res[v] < dv: continue
    #if v==goal: break
    for to,cost in [(10*v%k,0),((v+1)%k,1)]:
        #print(to,cost)
        if dv + cost < res[to]:
            res[to] = dv + cost
            if cost: q.append((res[to],to))
            else: q.appendleft((res[to],to))
    #print(res)
    
print((res[0]))
# Original solution
import sys
aa=list(map(int,sys.stdin.read().split()))
aa=aa[1:]
n=len(aa)
import bisect
bb=[]
for i in range(n):
    if not bb:
        bb.append(aa[i])
    else:
        if bb[0] >= aa[i]:
            if bb[-1] == aa[i]:
                bb.append(aa[i])
            else:
                bb.insert(0, aa[i])
        else:
            j = bisect.bisect_left(bb,aa[i])
            bb[j-1] = aa[i]
print((len(bb)))

# Optimized solution
import sys
aa=list(map(int,sys.stdin.read().split()))
aa=aa[1:aa[0]+1]
n=len(aa)
import bisect
bb=[]
for i in range(n):
    if not bb:
        bb.append(aa[-i-1])
    else:
        if bb[-1] <= aa[-i-1]:
            bb.append(aa[-i-1])
        else:
            j = bisect.bisect_right(bb,aa[-i-1])
            bb[j] = aa[-i-1]
print((len(bb)))
# Original solution
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N = _I()
A = [_I() for i in range(N)]

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

res = [] 
for a in A:
    #  print('a res', a, res)
    if len(res) == 0:
        res.append(a)
    else:
        if a <= res[-1]:
            # 小さいので追加
            res.append(a)
        else:
            # 入れ替え
            p = bisect(res, a, lambda x, y: x > y)
            while res[p] == a:
                p+=1
            else:
                res[p] = a

print(len(res))


# Optimized solution
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N = _I()
A = [_I() for i in range(N)]

"""
何個色を使えば塗れるか
最も小さい数字からはじめれば？
最も左からはじめれば？
"""

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

res = [] 
for a in A:
    #  print('a res', a, res)
    if len(res) == 0:
        res.append(a)
    else:
        if a <= res[-1]:
            # 小さいので追加
            res.append(a)
        else:
            # 入れ替え
            p = bisect(res, a, lambda x, y: x > y)
            if res[p] == a:
                p = bisect(res, a-1, lambda x, y: x > y)
                res[p] = a
            else:
                res[p] = a

print(len(res))
# Original solution
import bisect

def main():
  N = int(eval(input()))
  ans = 1
  lis_min = [int(eval(input()))]
  for i in range(N-1):
    a = int(eval(input()))
    index = bisect.bisect_left(lis_min, a)
    if index != 0:
      lis_min[index-1] = a
    else:
      ans += 1
      lis_min.insert(index, a)
  print(ans)
if __name__ == "__main__":
  main()
      

# Optimized solution
def bisect_right_reverse(a, x):
    '''
    reverseにソートされたlist aに対してxを挿入できるidxを返す。
    xが存在する場合には一番右側のidx+1となる。
    '''
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    # 二分探索
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

def main():
  N = int(eval(input()))
  ans = 1
  lis_min = [int(eval(input()))]
  for i in range(N-1):
    a = int(eval(input()))
    index = bisect_right_reverse(lis_min, a)
    if index != len(lis_min):
      lis_min[index] = a
    else:
      ans += 1
      lis_min.append(a)
  print(ans)
if __name__ == "__main__":
  main()
# Original solution
import bisect

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


colors = []

#後ろから見ていく
for i,n in enumerate(list(reversed(A))):
    # 一つ目はとりあえずなんか一色ぬる
    if i == 0:
        colors.append(n)
    else:
        #二つ目以降は、各色の最小値のなかで、今見ているのより小さいものがあればそれを置き換える
        #ここをbisect_leftにすると、colorsの中で同じ最小値があるときにinsertが必要なので遅い
        # 「各色の最小値集合の最小値と置き換える」を繰り返すので、最小値集合の最大より大きいなら最後に追加
        idx = bisect.bisect_right(colors, n)
        if idx == len(colors):
            colors.append(n)
        else:
            colors[idx] = n

print((len(colors)))

# Optimized solution
import bisect

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


colors = []

#後ろから見ていく
for i,n in enumerate(list(reversed(A))):
    # 一つ目はとりあえずなんか一色ぬる
    if i == 0:
        colors.append(n)
    else:
        #二つ目以降は、各色の最小値のなかで、今見ているのより小さいものがあればそれを置き換える
        # 「各色の最小値集合の最小値と置き換える」を繰り返すので、最小値集合の最大より大きいなら最後に追加
        idx = bisect.bisect_right(colors, n)
        #if idx == len(colors):
        if colors[-1] <= n:
            colors.append(n)
        else:
            colors[idx] = n

print((len(colors)))
# Original solution
N = int(eval(input()))
A = []
for i in range(N):
    A.append(int(eval(input())))
Minimum = [[A[0]]]
for i in range(1,N):
    Q = Minimum[i-1].copy()
    if A[i] <= min(Q):
        Q = [A[i]]+Q
    elif A[i] > max(Q):
        Q[len(Q)-1] = A[i]
    else:
        for j in range(len(Q)):
            if Q[j-1] < A[i] and A[i] <= Q[j]:
                Q[j-1] = A[i]
    Minimum.append(Q)
print((len(Minimum[N-1])))

# Optimized solution
N = int(eval(input()))
A = []
for i in range(N):
    A.append(int(eval(input())))
Minimum = [A[0]]
for i in range(1,N):
    if A[i] <= min(Minimum):
        Minimum = [A[i]]+Minimum
    elif A[i] > max(Minimum):
        Minimum[len(Minimum)-1] = A[i]
    else:
        for j in range(len(Minimum)):
            if Minimum[j-1] < A[i] and A[i] <= Minimum[j]:
                Minimum[j-1] = A[i]
print((len(Minimum)))
# Original solution
import bisect

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

x = []
for a in A:
    i = bisect.bisect_left(x,a)
    if i==0: x = [a] + x
    else: x[i-1]=a

print((len(x)))

# Optimized solution
import bisect

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

x = [A[0]]

for a in A[1:]:
    i = bisect.bisect(x,a)
    if i==len(x): x.append(a)
    else: x[i]=a

print((len(x)))
# Original solution
import bisect

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

if __name__ == "__main__":
    main()


# Optimized solution
import bisect

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

if __name__ == "__main__":
    main()
# Original solution
from bisect import bisect_right
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
A = [-a for a in A]

# dp[i] := 長さiの広義単調増加部分列を取る時の最大の数
dp = []
for a in A:
    i = bisect_right(dp, a)
    if i >= len(dp):
        dp.append(a)
    else:
        dp[i] = a

print((len(dp)))


# Optimized solution
from bisect import bisect_right
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
A = [-a for a in A]

X = []
for a in A:
    i = bisect_right(X, a)
    if i == len(X):
        X.append(a)
    else:
        X[i] = a


print((len(X)))
# Original solution
import bisect
N = int(eval(input()))
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(eval(input()))
now = [A[0]]

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


# Optimized solution
import bisect
N = int(eval(input()))
A = [0 for i in range(N)]
for i in range(N):
    A[i] = int(eval(input()))
now = [-A[0]]

for i in range(1, N):

    index = bisect.bisect_right(now, -A[i])
    if index == len(now):
        now.append(-A[i])
    else:
        now[index] = -A[i]

print((len(now)))
# Original solution
import sys
input = sys.stdin.readline
import bisect

INF = 10 ** 18
N = int(eval(input()))
A = [10 ** 10 - int(eval(input())) for _ in range(N)] # 逆順にしておく

# 最長単調減少列：狭義

dp = [INF] * (N+1) # 長さ、その長さの末端としてありうる最大値

for a in A:
    idx = bisect.bisect_right(dp,a)
    dp[idx] = a

answer = bisect.bisect_left(dp, INF)
print(answer)

# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from bisect import bisect_right

N,*A = list(map(int,read().split()))

def LIS(seq):
    # 狭義
    N = len(seq)
    INF = 10**18
    dp = [INF] * (N+1)
    for x in seq:
        i = bisect_right(dp,x)
        dp[i] = x
    return bisect_right(dp,INF-1)

answer = LIS([-x for x in A])
print(answer)
# Original solution
import math



def search2(S):
    harf = int(len(A)/2)
    for i, a in enumerate(A[harf:]):
        if a < S:
            A[i] = S
            return 
    return

def search(S):

    for i, a in enumerate(A):
        if a < S:
            A[i] = S
            return 
    return



def main():
    N = int(eval(input()))
    A[0] = int(eval(input()))
    m = A[0]
    harf = 0
    for _ in range(N-1):
        S = int(eval(input()))
        if S <= m:
            A.append(S)
        if S <= m:
            search2(S)
        else:
            search(S)
        m = A[-1]
        harf = A[int(len(A)/2)]
    print((len(A)))

    

if __name__ == "__main__":
    A = [0]
    main()


# Optimized solution
from bisect import bisect


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


if __name__ == "__main__":
    main()
# Original solution
N = int(eval(input()))
A = []
for _ in range(N):
    A.append(int(eval(input())))

def binsearch(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] >= threshold:
            right = mid
        else:
            left = mid
    return left


last=[]
for val in A:
    temp = binsearch(val, last)
    if temp == -1:
        #last.insert(0, val)
        last = [val] + last
    else:
        last[temp] = val
    #print(last)
print((len(last)))




# Optimized solution
N = int(eval(input()))
A = []
for _ in range(N):
    A.append(int(eval(input())))

def binsearch(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] < threshold:
            right = mid
        else:
            left = mid
    return right


last=[]
for val in A:
    temp = binsearch(val, last)
    if temp == len(last):
        #last.insert(0, val)
        last.append(val)
    else:
        last[temp] = val
    #print(last)
print((len(last)))
# Original solution
n = int(eval(input()))

arr = [0]*n
arr[0] = int(eval(input()))
color= [arr[0]]

for i in range(1, n):
	arr[i] = int(eval(input()))
	if arr[i] > color[-1]:
		color[-1] = arr[i]
	else:
		maxx = -1
		for idx, c in enumerate(color):
			if c < arr[i] and c > maxx:
				iidx = idx
				maxx = c
		if maxx != -1:
			color[iidx] = arr[i]
		else:
			color.append(arr[i])
print((len(color)))

# Optimized solution
from bisect import bisect

n = int(eval(input()))

seq = []
for i in range(n):
	ele = int(eval(input()))
	pos = bisect(seq, -ele)
	if len(seq) <= pos:
		seq.append(-ele)
	else:
		seq[pos] = -ele

print((len(seq)))
# Original solution
n = int(eval(input()))
l = [int(eval(input()))]
import bisect
from collections import deque
for i in range(1, n):
  a = int(eval(input()))
  p = bisect.bisect_left(l,a)
  if p == 0:
    l = deque(l)
    l.appendleft(a)
    l = list(l)
  else:
    l[p-1] = a

print((len(l)))

# Optimized solution
import bisect
from collections import deque

n = int(eval(input()))
l = deque([int(eval(input()))])

for i in range(1, n):
  a = int(eval(input()))
  p = bisect.bisect_left(l,a)
  if p == 0:
    l.appendleft(a)
  else:
    l[p-1] = a

print((len(l)))
# Original solution
n = int(eval(input()))
A = [int(eval(input())) for _ in range(n)]

B = []
import bisect
for i, a in enumerate(A):
    if len(B) == 0:
        B.append(-a)
    else:
        j = bisect.bisect_right(B, -a)
        #print(j)
        if j == len(B):
            B.append(-a)
        elif j == 0:
            B[0] = -a
        else:
            B[j] = -a
    #print(B)
#print(B)
print((len(B)))


# Optimized solution
n = int(eval(input()))
A = [int(eval(input())) for _ in range(n)]

A.reverse()

import bisect
B = [10**18]
for a in A:
    i = bisect.bisect_right(B, a)
    if 0 <= i < len(B):
        B[i] = a
    else:
        B.append(a)
print((len(B)))