CodeEff/ECCO huggingface dataset:
# Original solution
A, B = list(map(int, input().split()))


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


print((len(set(prime_decomposition(gcd(A, B)))) + 1))

# Optimized solution
A, B = list(map(int, input().split()))


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


print((len(set(prime_factorize(gcd(A, B)))) + 1))
# Original solution
import math

#input
a, b = list(map(int, input().split()))

# 2整数の公約数一覧 // 2num common divisor -> list
def commonDivisor (n1, n2):
    common_divisor=[]
    for i in range(2, min(n1, n2) + 1):
        if n1 % i == 0 and n2 % i == 0:
            common_divisor.append(i)
    return common_divisor

# 素数判定 // is prime? -> bool
def isPrime(n):
    if n != 2 and n % 2 == 0:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

cd = commonDivisor(a, b)
cd.insert(0, 1)
res = []
for num in cd:
    if isPrime(num) and res.count(num) == 0:
        res.append(num)

print(("{}".format(len(res))))

# Optimized solution
#input
a, b = list(map(int, input().split()))

# 最大公約数
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

n = gcd(a, b)
pf = factorization(n)
if pf == [[1, 1]]:
    print(("{}".format(len(pf))))
else:
    print(("{}".format(len(pf)+1)))
# Original solution
# ABC-142-D
A, B = list(map(int, input().split()))
ans = 1

#最大公約数
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def get_prime_number(x):
    if x == 1:
        return []
    max = int(x ** 0.5)
    search_list = [i for i in range(2,x+1)]
    prime_num = []
    while search_list[0] <= max:
        prime_num.append(search_list[0])
        tmp = search_list[0]
        search_list = [i for i in search_list if i % tmp != 0]
    prime_num.extend(search_list)
    return prime_num

#xの素因数を全て出す
def get_prime_factor(x):
    search_list = get_prime_number(x)
    prime_factor_list = []
    for i in search_list:
        if x % i == 0:
            prime_factor_list.append(i)
    return prime_factor_list

gcd_AB = gcd(A, B)
prime = get_prime_factor(gcd_AB)
ans += len(prime)
print(ans)

# Optimized solution
# ABC-142-D
A, B = list(map(int, input().split()))
ans = 1

#最大公約数
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def factorize(x):
    factor = []
    for num in range(2, int(x**0.5)+1):
        while x % num == 0:
            x //= num
            factor.append(num)
    if x != 1:
        factor.append(x)
    return set(factor)
    
gcd_AB = gcd(A, B)
prime = factorize(gcd_AB)
ans += len(prime)
print(ans)
# Original solution
import math

def is_prime(n):
    for p in range(2, int(math.sqrt(n)) + 1):
        if n % p == 0:
            return False
    return True

def prime_factorize(n):
    lst = []
    while n % 2 == 0:
        lst.append(2)
        n = n / 2
    a = 3
    while n > 1:
        if n % a == 0:
            lst.append(a)
            n = n / a
        else:
            a += 2
    return lst

A, B = list(map(int, input().split()))
lst = prime_factorize(min(A, B))
ret = 1
for n in set(lst):
    if is_prime(n) and A % n == 0 and B % n == 0:
        ret += 1

print(ret)

# Optimized solution
def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)
 
def prime_factorize(n):
    a = 2
    lst = []
    while a * a <= n:
        if n % a == 0:
            n = n / a
            lst.append(a)
        else:
            a += 1
    if n > 1:
        lst.append(n)
    return lst
 
A, B = list(map(int, input().split()))
n = gcd(A, B)
lst = prime_factorize(n)
print((len(set(lst)) + 1))
# Original solution
from itertools import combinations
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors


#nの素数判定
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

A, B = list(map(int, input().split()))

di_A = make_divisors(A)
di_B = make_divisors(B)

di_C = list(set(di_A) & set(di_B))
if len(di_C)==1:
    print((1))
    exit()

ans = 0
array = []
array_not = []
edges = [[False] * len(di_C) for _ in range(len(di_C))]
for i in range(len(di_C)):
    for j in range(i+1, len(di_C)):
        if gcd(di_C[i], di_C[j])==1:
            edges[i][j]=True

for num in range(len(di_C), 0, -1):
    fraction = combinations(list(range(len(di_C))), num)
    for relation in fraction:
        judge = []
        for i, j in combinations(relation, 2):
            judge.append(edges[i][j])
        if all(judge):
            ans = num
            print(ans)
            exit()
print(ans)



# Optimized solution


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr



A, B = list(map(int, input().split()))

fac_A = factorization(A)
fac_B = factorization(B)

prime_A = [f[0] for f in fac_A]
prime_B = [f[0] for f in fac_B]

if 1 in prime_A: prime_A.remove(1)
if 1 in prime_B: prime_B.remove(1)
common = set(prime_A) & set(prime_B)
print((len(common)+1))
# Original solution
from bisect import bisect_left
N = int(eval(input()))
A = list(int(eval(input())) for _ in range(N))
INF = 10 ** 9 + 1
V = [False for i in range(N)]
nv = 0
cnt = 0
while nv < N:
    dp = [INF]
    for i, a in enumerate(A):
        if V[i]:
            continue
        if a > dp[-1]:
            dp.append(a)
        else:
            j = bisect_left(dp, a)
            dp[j] = a
    nv += len(dp)
    dp.append(INF)
    m = len(dp)
    for i in range(N-1, -1, -1):
        if V[i]:
            continue
        if dp[m-1] <= A[i] < dp[m]:
            V[i] = True
            m -= 1
    cnt += 1

print(cnt)


# Optimized solution
from bisect import bisect_right
N = int(eval(input()))
A = list(int(eval(input())) for _ in range(N))
INF = 10 ** 9 + 1

dp = [INF]
for a in A:
    if -a >= dp[-1]:
        dp.append(-a)
    else:
        j = bisect_right(dp, -a)
        dp[j] = -a

print((len(dp)))
# Original solution
N = int(eval(input()))
As = [int(eval(input())) for _ in range(N)]
from bisect import bisect_right
from collections import deque

def LIS(L):
    dp = deque([L[0]])
    length = len(L)
    for i in range(1, length):
        a = L[i]
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a
    return dp

print((len(LIS(As[::-1]))))

# Optimized solution
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return list(map(int, input().split()))
sys.setrecursionlimit(10**9)

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

from bisect import bisect_right
lis = [1]
for a in As:
    if a>=lis[-1]:
        lis.append(a)
    else:
        lis[bisect_right(lis, a)] = a

print((len(lis)))
# Original solution
N = int(eval(input()))

A = []
for _ in range(N):
    a = int(eval(input()))
    A.append(a)
    
BALL = A[:]

from collections import defaultdict
COLOR = defaultdict(lambda: -1)

for b in BALL:
    i = 0
    while True:
        if COLOR[i] < b:
            COLOR[i] = b
            break
        i += 1
            
#print(COLOR)
print((len(COLOR)))


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

A = []
for _ in range(N):
    a = int(eval(input()))
    A.append(a)
    
nums = A[:]
colors = [float('inf')] * N

from bisect import bisect_left, bisect_right, insort_right
ans = 0
for n in nums:
    idx = bisect_right(colors, -n)
    colors[idx] = -n
    #print(ans)
    if idx > ans:
        ans = idx
    #print(idx, colors)
            
print((ans+1))
# Original solution
def bisect_right(a, x, lo=0, hi=None):
    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

import collections
n = int(eval(input()))
dat = []
for i in range(n):
    dat.append(int(eval(input())))
res = collections.deque([])

res.append(dat[0])
import bisect

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

    if a == len(res):
        res.append(dat[i])
    else:
        res[a] = dat[i]
print((len(res)))
#print(res)

# Optimized solution
n = int(eval(input()))
dat = []
for i in range(n):
    dat.append(int(eval(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)))
# Original solution
import bisect
from collections import deque

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

LDS = deque()
LDS.append(A[0])

for i in range(1,N):
    if LDS[0] >= A[i]:
        LDS.appendleft(A[i])
    else:
        LDS[bisect.bisect_left(LDS,A[i])-1] = A[i]

print((len(LDS)))

# Optimized solution
from bisect import bisect_left, bisect_right

def LIS(arr):  #bisect.bisect_left
    n = len(arr)
    lis = [arr[0]]
    for a in arr:
        if a > lis[-1]:
            lis.append(a)
        else:
            lis[bisect_left(lis, a)] = a
    return len(lis)

import sys
input = sys.stdin.readline

N = int(eval(input()))

A = []
for i in range(N):
    A.append((-int(eval(input())), i))

print((LIS(A)))
# Original solution
import bisect
N=int(eval(input()))
A=[]
for _ in range(N):
  A.append(int(eval(input())))

color=0
while A:#for i in range(10):
  color+=1
  LCS=[]
  inds=[]
  for i in range(len(A)):
    sny=bisect.bisect_left(LCS,A[i])
    if sny==len(LCS):
      LCS.append(A[i])
      if sny-1>=0:
        inds.append(inds[sny-1][:]+[i])
      else:
        inds.append([i])
    inds[sny][-1]=i
    LCS[sny]=A[i]
  #最長増加部分列を取り除く
  ind=0
  out=[]
  for i in range(len(A)-1,-1,-1):
    #print(inds[-1][-ind-1])
    if i==inds[-1][-ind-1]:
      ind+=1
      A.pop(i)
      #print(len(A))
      if ind >= len(LCS):
        break
print(color)
      
  
    
    
  
    
    
  
  
  

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

color=0
while A:#for i in range(10):
  color+=1
  LCS=[]
  inds=[]
  for i in range(len(A)):
    sny=bisect.bisect_left(LCS,A[i])
    if sny==len(LCS):
      LCS.append(A[i])
      if sny-1>=0:
        inds.append(i)
      else:
        inds.append(i)
    #inds[sny][-1]=i
    LCS[sny]=A[i]
  #最長増加部分列を取り除く
  ind=0
  out=[]
  for i in range(len(A)-1,-1,-1):
    #print(inds[-1][-ind-1])
    if i==inds[-ind-1]:
      ind+=1
      A.pop(i)
      #print(len(A))
      if ind >= len(LCS):
        break
print(color)
# Original solution
# YouTube解説の方法（deque使わない）
from bisect import bisect_left
import sys
input = sys.stdin.readline

def bisect_right_reverse(L, target):
    return len(L) - bisect_left(L[::-1], target)

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

L = []
for i in range(N):
    k = bisect_right_reverse(L, A[i])
    if k == len(L):
        L.append(A[i])
    else:
        L[k] = A[i]

print((len(L)))

# Optimized solution
# YouTube解説の方法（deque使わない）
import sys
input = sys.stdin.readline

def bisect_right_reverse(L, target):
    ok = len(L)
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if L[mid] < target:
            ok = mid
        else:
            ng = mid
    return ok

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

L = []
for i in range(N):
    k = bisect_right_reverse(L, A[i])
    if k == len(L):
        L.append(A[i])
    else:
        L[k] = A[i]

print((len(L)))
# Original solution
from collections import deque
import bisect

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

Q = deque([A[0]])
for a in A[1:]:
    if a <= Q[0]:
        Q.appendleft(a)
    else:
        idx = bisect.bisect_left(Q,a)
        Q[idx-1] = a

print((len(Q)))

# Optimized solution
import bisect

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

A.reverse()

dp = [A[0]]

for a in A[1:]:
    idx = bisect.bisect_right(dp, a)
    if idx == len(dp):
        dp.append(a)
    else:
        dp[idx] = a

print((len(dp)))
# Original solution
# 広義最長部分増加数列の長さを求めるdef
# 配列LIS自体は広義最長部分増加文字列ではない
import bisect
def lis(seq):
    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]
    return(len(LIS))

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

b = a[::-1]
print((lis(b)))

# Optimized solution
n = int(eval(input()))
a = []
for i in range(n):
    ai = int(eval(input()))
    a.append(ai)

lst = [a[0]]
for i in range(1, n):
    ai = a[i]
    left = -1
    right = len(lst)
    while left+1 < right:
        mid = (left + right) // 2
        if lst[mid] < ai:
            right = mid
        else:
            left = mid
    if right == len(lst):
        lst.append(ai)
    else:
        lst[right] = ai
print((len(lst)))
# Original solution
import bisect

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

Q = [A[0]] + [float("inf")] * (n+1)
le = 1
for i in range(1, n):
    if Q[le-1] >= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        ind = bisect.bisect_left(Q[:le][::-1], A[i])
        Q[le-ind] = A[i]
    # print(Q[:10])

print(le)

# Optimized solution
import bisect

n = int(eval(input()))
A = [-int(eval(input())) for i in range(n)]

Q = [A[0]] + [0] * (n+1)
le = 1
for i in range(1, n):
    if Q[le-1] <= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        ind = bisect.bisect_right(Q, A[i], 0, le)
        Q[ind] = A[i]
    # print(Q[:10])

print(le)
# Original solution
import bisect
from collections import deque

N = int(eval(input()))

# c = [int(input())]
c = deque()
c.appendleft(int(eval(input())))


for ai in range(1, N):
    a = int(eval(input()))
    if a <= c[0]:
        c.appendleft(a)
    else:
        i = bisect.bisect_left(c, a) - 1
        c[i] = a

print((len(c)))


# Optimized solution
# -*- coding utf-8 -*-
import bisect
from collections import deque

N = int(eval(input()))

# c = [int(input())]
c = deque()
c.appendleft(int(eval(input())))


for ai in range(1, N):
    a = int(eval(input()))
    if a <= c[0]:
        c.appendleft(a)
    else:
        i = bisect.bisect_left(c, a) - 1
        c[i] = a

print((len(c)))
# Original solution
from collections import deque
from bisect import bisect_left

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

t = deque([A[0]])
for a in A[1:]:
    if a <= t[0]:
        t.appendleft(a)
    else:
        t[bisect_left(t, a) - 1] = a
print((len(t)))


# Optimized solution
from bisect import bisect_right

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

t = [-A[0]]
for a in A[1:]:
    if a <= -t[-1]:
        t.append(-a)
    else:
        t[bisect_right(t, -a)] = -a
print((len(t)))
# Original solution
from collections import deque
from bisect import bisect_left

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

t = deque([A[0]])
for a in A[1:]:
    i = bisect_left(t, a) - 1
    if i == -1:
        t.appendleft(a)
    else:
        t[i] = a
print((len(t)))


# Optimized solution
from bisect import bisect_right

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

t = [-A[0]]
for a in A[1:]:
    if a <= -t[-1]:
        t.append(-a)
    else:
        t[bisect_right(t, -a)] = -a
print((len(t)))
# Original solution
def LIS(A):
    dp = deque([A[0]])
    for a in A[1:]:
        if a <= dp[0]:
            dp.appendleft(a)
        else:
            dp[bisect_left(dp, a)-1] = a
    return len(dp)

##################################################################################################################

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

N = int(eval(input()))

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

print((LIS(A)))

# Optimized solution
def LIS(A):
    dp = [-A[0]]
    for a in A[1:]:
        if -a >= dp[-1]:
            dp.append(-a)
        else:
            dp[bisect_right(dp, -a)] = -a
    return len(dp)

##################################################################################################################

import sys
input = sys.stdin.readline
from bisect import *

N = int(eval(input()))

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

print((LIS(A)))
# Original solution
from heapq import *
from bisect import bisect_right, bisect_left
from collections import deque
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
lb, ub = 0, N
while lb + 1 < ub:
    mid = (lb+ub)//2
    cnt, ms, flag = 1, deque(), 1
    ms.append(A[0])
    for a in A[1:]:
        if a <= ms[0]:
            ms.appendleft(a)
            cnt += 1
            if cnt > mid:
                flag = 0
                break
        else:
            i = bisect_left(ms, a)-1
            ms[i] = a
    if flag:
        ub = mid
    else:
        lb = mid
cnt, ms, flag = 1, deque(), 1
ms.append(A[0])
for a in A[1:]:
    if a <= ms[0]:
        ms.appendleft(a)
        cnt += 1
        if cnt > mid:
            flag = 0
            break
    else:
        i = bisect_left(ms, a)-1
        ms[i] = a
if flag:
    print(mid)
else:
    print((mid+1))


# Optimized solution
from bisect import bisect_left
from collections import deque
N = int(eval(input()))
A = [int(eval(input())) for i in range(N)]
cnt, ms, flag = 1, deque(), 1
ms.append(A[0])
for a in A[1:]:
    if a <= ms[0]:
        ms.appendleft(a)
        cnt += 1
    else:
        i = bisect_left(ms, a)-1
        ms[i] = a
print(cnt)
# Original solution
from bisect import bisect_left
from collections import deque

def main():
    inf=float("inf")
    sm=1
    n=int(eval(input()))
    alst=[inf]*n
    work=[inf]*n
    index_list=[inf]*n
    for i in range(n):
        a=int(eval(input()))
        alst[i]=a
        j=bisect_left(work,a)
        work[j]=a
        index_list[j]=i
    alst=[x for i,x in enumerate(alst) if not i in index_list]

    while alst:
        sm+=1
        n=len(alst)
        work=[inf]*n
        index_list=[inf]*n
        for i in range(n):
            a=alst[i]
            j=bisect_left(work,a)
            work[j]=a
            index_list[j]=i
        alst=[x for i,x in enumerate(alst) if not i in index_list]
    print(sm)

main()

# Optimized solution
from bisect import bisect_right

def main():
    inf=float("inf")
    n=int(eval(input()))
    alst=[int(eval(input())) for _ in range(n)]
    work=[inf]*n
    for i in range(n-1,-1,-1):
        j=bisect_right(work,alst[i])
        work[j]=alst[i]
    print((n-work.count(inf)))

main()
# Original solution
from bisect import bisect_left, bisect_right

n = int(eval(input()))
col_maxs = []
for _ in range(n):
    a = int(eval(input())) * (-1)
    if not col_maxs:
        col_maxs.append(a)
        continue

    curr_max = col_maxs[-1]
    if a >= curr_max:
        col_maxs.append(a)
    else:
        # aより大きい最小要素のindex/value
        ind = bisect_right(col_maxs, a)
        col_maxs[ind] = a

print((len(col_maxs)))

# Optimized solution
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

n = int(eval(input()))
col_maxs = []
for _ in range(n):
    a = int(eval(input())) * (-1)
    if not col_maxs:
        col_maxs.append(a)
        continue

    curr_max = col_maxs[-1]
    if a >= curr_max:
        col_maxs.append(a)
    else:
        # aより大きい最小要素のindex/value
        ind = bisect_right(col_maxs, a)
        col_maxs[ind] = a

print((len(col_maxs)))
# Original solution
# -*- coding: utf-8 -*-
# E - Sequence Decomposing
import sys 
from bisect import bisect_left
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,read().split()))


INF = 10**31
q = deque([])

for a in A:
    idx = bisect_left(q, a)
    if idx == 0:
        q.appendleft(a)
    else:
        q[idx-1] = a
print((len(q)))

# Optimized solution
# -*- coding: utf-8 -*-
# E - Sequence Decomposing
import sys 
from bisect import bisect_right

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,read().split()))
X = [-1]*N
for a in A:
    i = bisect_right(X,a-1)-1
    X[i] = a
print((N - X.count(-1)))
# Original solution
from bisect import bisect_left
from collections import deque

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

q = deque([-1])
for x in a:
    insert_pos = bisect_left(q, x) - 1
    # bisect_left[0,len(lis)] == 以上の最小
    # 手前は未満の最大[-1,len(lis))
    if insert_pos == -1:
        q.appendleft(x)
    else:
        q[insert_pos] = x

ret = len(q)

print(ret)

# 最小パス被覆


# Optimized solution
# LDS最長減少部分列
# 解説放送
# dilworthの定理
# パスを通してどの2点間も移動できないような点集合の点の個数 = 最小パス被覆
# 移動できないような点は
# 右側（大きい値側）から見て以上になっているような数列

from bisect import bisect_right

inf = 10 ** 9 + 1

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

t = [inf]
for x in reversed(a):
    if t[-1] <= x:
        t.append(x)
    else:
        insert_pos = bisect_right(t, x)
        t[insert_pos] = x

ret = len(t)

print(ret)
# Original solution
from bisect import bisect

icase=0
if icase==0:
    n=int(eval(input()))
    a=[0]*n
    for i in range(n):
        a[i]=int(eval(input()))

def loopa(a):

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -1
    dq = [0]*(n+1)    
    
    for i in range(n):
        idx = bisect(dp, a[i]-1)
        if dp[idx]==10**10:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i
            dp2=dp[1:idx+1]
            dq2=dq[1:idx+1]
        else:
#            dp[idx] = min(a[i], dp[idx])
            if dp[idx]>a[i]:
                dp[idx]=a[i]
                dq[idx]=i


#    dq2.sort() 
#    for i in range(len(dq2)-1,-1,-1):
#        del a[dq2[i]]
#    print(dq2)
    a=[a[i] for i in range(n) if not (i in dq2)]
    return a

icnt=0
while len(a)>0:
#    if icnt>10:break
    a=loopa(a)        
    icnt+=1

print(icnt)    


# Optimized solution
from bisect import bisect

icase=1
if icase==1:
    n=int(eval(input()))
    a=[0]*n
    for i in range(n):
        a[i]=-int(eval(input()))
elif icase==2:
    n=5
    a=[-2,-1,-4,-5,-3]
elif icase==3:
    n=4
    a=[0,0,0,0]

def loopa():

    n=len(a)
    dp = [10**10]*(n+1)
    dp[0] = -10**10
    
    for i in range(n):
#        idx = bisect(dp, a[i]-1)
        idx = bisect(dp, a[i])
        dp[idx] = min(a[i], dp[idx])

#        print("i:",i,"a:",a,"dp2:",dp2)            
    return dp

dp=loopa()        

print((bisect(dp, 10**10-1)-1))