An Introduction to the Longest Increasing Subsequence Problem  

The task is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in strictly ascending order. This is called the Longest Increasing Subsequence (LIS) problem.

For example, the length of the LIS for $[15,27,14,38,26,55,46,65,85]$ is $\boldsymbol{6}$ since the longest increasing subsequence is $[15,27,38,55,65,85]$.  

Here's a great YouTube video of a lecture from MIT's Open-CourseWare covering the topic.  

This is one approach which solves this in quadratic time using dynamic programming. A more efficient algorithm which solves the problem in $O(n\log n)$ time is available here. 

Given a sequence of integers, find the length of its longest strictly increasing subsequence.

Function Description  

Complete the longestIncreasingSubsequence function in the editor below.  It should return an integer that denotes the array's LIS.  

longestIncreasingSubsequence has the following parameter(s):  

arr: an unordered array of integers  

Input Format

The first line contains a single integer $n$, the number of elements in $\textbf{arr}$. 

Each of the next $n$ lines contains an integer, $arr\left[i\right]$

Constraints

$1\leq n\leq10^{6}$  
$1\leq ar r[i]\leq10^5$  

Output Format

Print a single line containing a single integer denoting the length of the longest increasing subsequence.

Sample Input 0
5
2
7
4
3
8

Sample Output 0
3

Explanation 0

In the array $arr=[2,7,4,3,8]$, the longest increasing subsequence is $[2,7,8]$.  It has a length of $3$.

Sample Input 1
6
2
4
3
7
4
5

Sample Output 1
4

Explanation 1

The LIS of $arr=[2,4,3,7,4,5]$ is $[2,3,4,5]$.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def subsequence(seq):
	if not seq:
		return seq
	M = [None] * len(seq)
	P = [None] * len(seq)
	L = 1
	M[0] = 0
	for i in range(1, len(seq)):
		lower = 0
		upper = L
		if seq[M[upper - 1]] < seq[i]:
			j = upper
		else:
			while upper - lower > 1:
				mid = (upper + lower) // 2
				if seq[M[mid - 1]] < seq[i]:
					lower = mid
				else:
					upper = mid
			j = lower
		P[i] = M[j - 1]
		if j == L or seq[i] < seq[M[j]]:
			M[j] = i
			L = max(L, j + 1)
	result = []
	pos = M[L - 1]
	for _ in range(L):
		result.append(seq[pos])
		pos = P[pos]
	return result[::-1]
i = 0
import sys
seq = []
i = 0
for line in sys.stdin:
	if i == 0:
		i += 1
	else:
		seq.append(int(line.split()[0]))
print(len(subsequence(seq)))


import bisect
N = int(input())
A = [int(input()) for c in range(N)]
P = [0] * N
M = [0] * (N + 1)
L = 0
for i in range(N):
	(lo, hi) = (1, L)
	while lo <= hi:
		mid = lo + (hi - lo) // 2
		if A[M[mid]] < A[i]:
			lo = mid + 1
		else:
			hi = mid - 1
	newL = lo
	P[i] = M[newL - 1]
	M[newL] = i
	if newL > L:
		L = newL
print(L)


def subsequence(seq):
	if not seq:
		return seq
	M = [None] * len(seq)
	P = [None] * len(seq)
	L = 1
	M[0] = 0
	for i in range(1, len(seq)):
		lower = 0
		upper = L
		if seq[M[upper - 1]] < seq[i]:
			j = upper
		else:
			while upper - lower > 1:
				mid = (upper + lower) // 2
				if seq[M[mid - 1]] < seq[i]:
					lower = mid
				else:
					upper = mid
			j = lower
		P[i] = M[j - 1]
		if j == L or seq[i] < seq[M[j]]:
			M[j] = i
			L = max(L, j + 1)
	result = []
	pos = M[L - 1]
	for _ in range(L):
		result.append(seq[pos])
		pos = P[pos]
	return result[::-1]
i = 0
import sys
seq = []
i = 0
for line in sys.stdin:
	if i == 0:
		i += 1
	else:
		seq.append(int(line.split()[0]))
print(len(subsequence(seq)))


import sys

def getLIS(A):
	(M, P, L) = ([None], [], 0)
	for (i, a) in enumerate(A):
		(lo, hi) = (0, L)
		while hi > lo:
			mi = (hi + lo + 1) // 2
			if A[M[mi]] >= a:
				hi = mi - 1
			else:
				lo = mi
		newL = lo + 1
		P.append(M[newL - 1])
		if newL > L:
			M.append(i)
			L = newL
		elif A[M[newL]] > a:
			M[newL] = i
	S = []
	m = M[L]
	while m != None:
		S.append(A[m])
		m = P[m]
	return S[::-1]
N = int(input())
A = [int(input()) for _ in range(N)]
S = getLIS(A)
print(S, file=sys.stderr)
print(len(S))


from math import ceil
n = int(input())
X = [int(input()) for i in range(n)]
P = [0 for i in range(n)]
M = [0 for i in range(n)]
L = 0
for i in range(n):
	lo = 1
	hi = L
	while lo <= hi:
		mid = ceil((lo + hi) / 2)
		if X[M[mid]] < X[i]:
			lo = mid + 1
		else:
			hi = mid - 1
	newL = lo
	M[newL] = i
	if newL > L:
		L = newL
print(L)


N = int(input())
lst = []
for i in range(N):
	num = int(input())
	lst.append(num)

def insert(num, arr):
	lft = 0
	l = len(arr)
	rgt = l - 1
	while lft <= rgt:
		mid = (lft + rgt) // 2
		if num > arr[mid]:
			lft = mid + 1
		else:
			rgt = mid - 1
	if lft == l:
		arr.append(num)
	else:
		arr[lft] = num
arr = [lst[0]]
for i in range(1, N):
	insert(lst[i], arr)
print(len(arr))


n = int(input())
array = [0]
for i in range(n):
	array.append(int(input()))
min_seq_end_wth_len = [0]
length = 0
for i in range(1, n + 1):
	low = 0
	high = length
	while low <= high:
		mid = (low + high) // 2
		if array[min_seq_end_wth_len[mid]] < array[i]:
			low = mid + 1
		else:
			high = mid - 1
	max_len = low
	if max_len > length:
		length = max_len
		min_seq_end_wth_len.append(i)
	if array[i] < array[min_seq_end_wth_len[max_len]]:
		min_seq_end_wth_len[max_len] = i
print(length)


vector_length = int(input())
longest_LIS = 1
length_LIS_dict = {}
length_LIS_dict[1] = int(input())
for i in range(vector_length - 1):
	low = 1
	high = longest_LIS
	current_number = int(input())
	while low <= high:
		mid = (low + high + 1) // 2
		if current_number > length_LIS_dict[mid]:
			low = mid + 1
		else:
			high = mid - 1
	if low > longest_LIS:
		longest_LIS = low
	length_LIS_dict[low] = current_number
print(longest_LIS)


import math

def LIS(a):
	M = [0 for x in range(len(a) + 1)]
	L = 0
	for i in range(len(a)):
		lo = 1
		hi = L
		while lo <= hi:
			mid = math.ceil((lo + hi) / 2)
			if a[M[mid]] < a[i]:
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		M[newL] = i
		if newL > L:
			L = newL
	return L
N = int(input())
a = []
for i in range(N):
	a.append(int(input()))
print(LIS(a))


from math import ceil

def LIS(X):
	N = len(X)
	P = [0] * N
	M = [0] * (N + 1)
	L = 0
	for i in range(N):
		lo = 1
		hi = L
		while lo <= hi:
			mid = ceil((lo + hi) / 2)
			if X[M[mid]] < X[i]:
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		P[i] = M[newL - 1]
		M[newL] = i
		if newL > L:
			L = newL
	return L
d = []
for i in range(int(input())):
	d.append(int(input()))
print(LIS(d))


import unittest
from bisect import bisect_left

def LIS(S):
	head = []
	tail = [None]
	for x in S:
		i = bisect_left(head, x)
		if i >= len(head):
			head.append(x)
			if i > 0:
				tail.append((head[i - 1], tail[i - 1]))
		elif head[i] > x:
			head[i] = x
			if i > 0:
				tail[i] = (head[i - 1], tail[i - 1])
	if not head:
		return []
	output = [head[-1]]
	pair = tail[-1]
	while pair:
		(x, pair) = pair
		output.append(x)
	output.reverse()
	return output
N = int(input())
lis = list((int(input()) for i in range(N)))
res = LIS(lis)
print(len(res))


import bisect
N = int(input())
a = []
for i in range(N):
	a.append(int(input()))
M = [a[0]]
for i in range(1, N):
	idx = bisect.bisect_left(M, a[i])
	if idx == len(M):
		M.append(a[i])
	else:
		M[idx] = min(M[idx], a[i])
print(len(M))


import os, sys, itertools
N = int(input())
A = [0] * N
X = [None] * N
for i in range(N):
	A[i] = int(input())
size = 0
for val in A:
	(l, r) = (-1, size)
	while r - l > 1:
		m = l + (r - l) // 2
		if X[m] == None or X[m] >= val:
			r = m
		else:
			l = m
	X[r] = val
	size = max(size, r + 1)
it = 0
while it < len(X) and X[it] != None:
	it = it + 1
print(it)


import math

def LIS():
	N = int(input())
	seq = []
	for i in range(N):
		seq.append(int(input()))
	lis = [1]
	for i in range(1, N):
		currentL = max([lis[j] for j in range(len(lis)) if seq[j] < seq[i]]) + 1
		lis.append(currentL)
	print(max(lis))

def LIS2():
	N = int(input())
	seq = []
	for i in range(N):
		seq.append(int(input()))
	M = [0 for i in range(N - 1)]
	L = 0
	for i in range(N):
		lo = 1
		hi = L
		while lo <= hi:
			mid = math.ceil((lo + hi) / 2)
			if seq[M[mid]] < seq[i]:
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		M[newL] = i
		if newL > L:
			L = newL
	print(L)
LIS2()


import math

def lis(lst):
	prev = [-1 for i in range(len(lst))]
	last_indices = [0]
	length = 1
	last_indices.append(0)
	for i in range(1, len(lst)):
		low = 1
		high = length
		while low <= high:
			mid = math.ceil((low + high) / 2)
			if lst[last_indices[mid]] < lst[i]:
				low = mid + 1
			else:
				high = mid - 1
		if low == 1:
			prev[low] = -1
		else:
			prev[low] = last_indices[low - 1]
		try:
			last_indices[low] = i
		except IndexError:
			last_indices.append(i)
		length = max(low, length)
	return length
length = int(input())
lst = []
for i in range(length):
	el = int(input())
	lst.append(el)
print(lis(lst))


class Tableau:

	def __init__(self):
		self.nrows = 1
		self.t = list()
		self.t.append(list())

	def insert_elem(self, e):
		self.insert_into_row(e, 0)

	def insert_into_row(self, e, row):
		if len(self.t[row]) == 0:
			self.t[row].append(e)
			return
		if e >= self.t[row][-1]:
			self.t[row].append(e)
			return
		start = 0
		end = len(self.t[row]) - 1
		while start < end:
			mid = start + (end - start) // 2
			assert mid >= start and mid < end
			if self.t[row][mid] < e:
				start = mid + 1
			else:
				end = mid
		assert start == end
		self.t[row][start] = e

	def get_lis(self):
		lis = 0
		for i in range(self.nrows):
			if len(self.t[i]) > lis:
				lis = len(self.t[i])
		return lis
t = Tableau()
n = int(input().strip())
for i in range(n):
	t.insert_elem(int(input().strip()))
print(t.get_lis())


import math
N = int(input())
top_ele = []
piles = []

def find_pos(ele):
	lo = 0
	hi = len(top_ele) - 1
	while lo <= hi:
		mid = math.ceil((lo + hi) / 2)
		if top_ele[mid] >= ele:
			hi = mid - 1
		else:
			lo = mid + 1
	if hi == len(top_ele) - 1:
		top_ele.append(ele)
		return -1
	else:
		top_ele[hi + 1] = ele
		return hi + 1
for i in range(0, N):
	ele = int(input())
	x = find_pos(ele)
	if x == -1:
		pile = [ele]
		piles.append(pile)
	else:
		piles[x].append(ele)
print(len(piles))


def ceilIndex(L, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if L[m] >= key:
			r = m
		else:
			l = m
	return r

def LIS(A):
	tailTable = []
	tailTable.append(A[0])
	Len = 1
	for i in range(1, len(A)):
		if A[i] < tailTable[0]:
			tailTable[0] = A[i]
		elif A[i] > tailTable[-1]:
			Len += 1
			tailTable.append(A[i])
		else:
			tailTable[ceilIndex(tailTable, -1, Len - 1, A[i])] = A[i]
	return Len
print(LIS([int(input()) for i in range(int(input()))]))


size = int(input())
lst = []
for _ in range(size):
	lst.append(int(input()))

def find_index(lst, lo, hi, item):
	while hi > lo + 1:
		mid = lo + (hi - lo) // 2
		if lst[mid] >= item:
			hi = mid
		else:
			lo = mid
	return hi
tail_lst = [0] * size
tail_lst[0] = lst[0]
curr = 1
for i in range(1, size):
	if lst[i] < tail_lst[0]:
		tail_lst[0] = lst[i]
	elif lst[i] > tail_lst[curr - 1]:
		tail_lst[curr] = lst[i]
		curr += 1
	else:
		tail_lst[find_index(tail_lst, -1, curr - 1, lst[i])] = lst[i]
print(curr)


from collections import namedtuple
from functools import total_ordering
from bisect import bisect_left

@total_ordering
class Node(namedtuple('Node_', 'val back')):

	def __iter__(self):
		while self is not None:
			yield self.val
			self = self.back

	def __lt__(self, other):
		return self.val < other.val

	def __eq__(self, other):
		return self.val == other.val

def lis(d):
	if not d:
		return []
	pileTops = []
	for di in d:
		j = bisect_left(pileTops, Node(di, None))
		new_node = Node(di, pileTops[j - 1] if j > 0 else None)
		if j == len(pileTops):
			pileTops.append(new_node)
		else:
			pileTops[j] = new_node
	return list(pileTops[-1])[::-1]
T = int(input())
A = []
for _ in range(T):
	A.append(int(input()))
print(len(lis(A)))


import math

def max_increasing_subsequence2(L):
	P = [0 for i in range(len(L))]
	M = [0 for i in range(len(L) + 1)]
	longest_length_so_far = 0
	for i in range(len(L)):
		low = 1
		high = longest_length_so_far
		while low <= high:
			mid = math.ceil((low + high) / 2)
			if L[M[mid]] < L[i]:
				low = mid + 1
			else:
				high = mid - 1
		new_longest_length_so_far = low
		P[i] = M[new_longest_length_so_far - 1]
		M[new_longest_length_so_far] = i
		if new_longest_length_so_far > longest_length_so_far:
			longest_length_so_far = new_longest_length_so_far
	S = [0 for i in range(longest_length_so_far)]
	k = M[longest_length_so_far]
	for i in range(longest_length_so_far - 1, -1, -1):
		S[i] = L[k]
		k = P[k]
	return len(S)

def max_increasing_subsequence1(L):
	longest = []
	current = []
	longest.append([L[0]])
	for i in range(1, len(L)):
		for j in range(i):
			if L[j] < L[i] and len(current) < len(longest[j]) + 1:
				current = longest[j]
		longest.append(current + [L[i]])
		current = []
	longest_subseq_length = 0
	for seq in longest:
		length = len(seq)
		if length > longest_subseq_length:
			longest_subseq_length = length
	return longest_subseq_length
arr_len = int(input())
arr = []
for i in range(arr_len):
	arr.append(int(input()))
print(max_increasing_subsequence2(arr))


import math

def search(A, T, l, r, key):
	while l <= r:
		m = int(math.ceil((l + r) / 2))
		if A[T[m]] < key:
			l = m + 1
		else:
			r = m - 1
	return l

def lis(s, N):
	T = [0 for i in range(N + 1)]
	ln = 0
	for i in range(0, N):
		pos = search(s, T, 1, ln, s[i])
		T[pos] = i
		if pos > ln:
			ln = pos
	return ln
N = int(input())
seq = []
for i in range(N):
	seq.append(int(input()))
print('{}'.format(lis(seq, N)))


import array

def bin_search(li, arr, item, low, high):
	while low <= high:
		mid = low + (high - low) // 2
		if arr[li[mid]] < item:
			low = mid + 1
		else:
			high = mid - 1
	return low

def lis(arr):
	if not arr:
		return 0
	max_length = 0
	last_index = [-1] * len(arr)
	last_index[max_length] = 0
	for (idx, item) in enumerate(arr):
		pos = bin_search(last_index, arr, item, 0, max_length)
		last_index[pos] = idx
		if pos > max_length:
			max_length = pos
	return max_length + 1
n = int(input())
arr = array.array('Q')
while n:
	try:
		arr.append(int(input()))
	except EOFError:
		pass
	n -= 1
print(lis(arr))


from bisect import bisect

def lis(seq):
	best = [()]
	for i in seq:
		ind = bisect(best, (i,))
		if ind == len(best):
			best.append((i, best[-1]))
		else:
			best[ind] = (i, best[ind - 1])
	return len(best) - 1
size = int(input())
seq = [int(input()) for _ in range(size)]
print(lis(seq))


import bisect

def lis(a):
	cache = []
	for i in range(len(a)):
		j = bisect.bisect_left(cache, a[i])
		if j == len(cache):
			cache.append(a[i])
		else:
			cache[j] = a[i]
	return len(cache)
n = int(input())
l = [None] * n
for i in range(n):
	l[i] = int(input())
print(lis(l))


N = int(input())
arr = [int(input()) for _ in range(N)]
piles = [[arr[0]]]
for a in arr[1:]:
	found = False
	(lo, hi) = (0, len(piles) - 1)
	while lo < hi:
		m = (hi + lo) // 2
		if piles[m][-1] >= a:
			hi = m
		else:
			lo = m + 1
	if not piles[lo][-1] >= a:
		piles.append([a])
	else:
		piles[lo].append(a)
print(len(piles))


def modBinarySearch(arr, value):
	start = 0
	end = len(arr)
	while start + 1 < end:
		mid = int((start + end) / 2)
		if value < arr[mid]:
			end = mid
		elif value > arr[mid]:
			start = mid
		else:
			return mid
	return end

def findLIS(lst):
	longestIncreatingSubsequence = []
	longestIncreatingSubsequence.append(lst[0])
	for element in lst[1:]:
		if element <= longestIncreatingSubsequence[0]:
			longestIncreatingSubsequence[0] = element
		elif element > longestIncreatingSubsequence[-1]:
			longestIncreatingSubsequence.append(element)
		else:
			foo = modBinarySearch(longestIncreatingSubsequence, element)
			if foo > -1:
				longestIncreatingSubsequence[foo] = element
	return len(longestIncreatingSubsequence)
N = int(input())
lst = []
for i in range(N):
	lst.append(int(input()))
print(findLIS(lst))


import math

def findLIS(a):
	M = [0] * (len(a) + 1)
	L = 0
	for i in range(0, len(a)):
		low = 1
		high = L
		while low <= high:
			mid = int(math.ceil((low + high) / 2))
			if a[M[mid]] < a[i]:
				low = mid + 1
			else:
				high = mid - 1
		newL = low
		M[newL] = i
		if newL > L:
			L = newL
	return L
N = int(input())
array = []
for i in range(N):
	array.append(int(input()))
result = findLIS(array)
print(result)


def find_lis(ls):
	lis = []
	for item in ls:
		if len(lis) == 0 or item > lis[-1]:
			lis.append(item)
			continue
		(low, high, res) = (0, len(lis) - 1, -1)
		while high >= low:
			middle = (high + low) // 2
			if lis[middle] < item:
				low = middle + 1
			elif lis[middle] > item:
				res = middle
				high = middle - 1
			else:
				res = middle
				break
		lis[res] = item
	return len(lis)
n = int(input())
res = []
for _ in range(n):
	res.append(int(input()))
print(find_lis(res))


from math import ceil

def calc_LIS(X):
	P = [0 for _ in range(len(X))]
	M = [0 for _ in range(len(X) + 1)]
	L = 0
	for i in range(len(X)):
		lo = 1
		hi = L
		while lo <= hi:
			mid = int(ceil((lo + hi) / 2))
			if X[M[mid]] < X[i]:
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		P[i] = M[newL - 1]
		M[newL] = i
		if newL > L:
			L = newL
	S = [0 for _ in range(L)]
	k = M[L]
	for i in range(L - 1, -1, -1):
		S[i] = X[k]
		k = P[k]
	return S
X = []
n = int(input())
for i in range(n):
	X.append(int(input()))
print(len(calc_LIS(X)))


import math
N = int(input())
X = []
for i in range(N):
	X.append(int(input()))
N = N + 1
P = [0 for x in range(N)]
M = [0 for x in range(N + 1)]
L = 0
for i in range(0, N - 1):
	lo = 1
	hi = L
	while lo <= hi:
		mid = math.ceil((lo + hi) / 2)
		mid = int(mid)
		if X[M[mid]] < X[i]:
			lo = mid + 1
		else:
			hi = mid - 1
	newL = lo
	P[i] = M[newL - 1]
	M[newL] = i
	if newL > L:
		L = newL
print(L)


def lis(N, A):
	T = [0 for _ in range(N)]
	P = [0 for _ in range(N)]
	L = 1

	def get_ceil_index(L, R, K):
		while R - L > 1:
			M = L + (R - L) // 2
			if A[T[M]] >= K:
				R = M
			else:
				L = M
		return R
	for i in range(1, N):
		if A[i] < A[T[0]]:
			T[0] = i
		elif A[i] > A[T[L - 1]]:
			T[L] = i
			L += 1
		else:
			p = get_ceil_index(-1, L - 1, A[i])
			P[i] = T[p - 1]
			T[p] = i
	return L

def main():
	N = int(input())
	A = [int(input()) for _ in range(N)]
	print(lis(N, A))
main()


import bisect
n = int(input())
nums = [int(input().strip()) for i in range(n)]
dp = [None] * n
dp[0] = nums[0]
maxi = 1
for i in range(1, n):
	k = bisect.bisect_left(dp, nums[i], lo=0, hi=maxi)
	maxi = max(maxi, k + 1)
	dp[k] = nums[i]
print(maxi)


from bisect import bisect_left
n = int(input().strip())
if n == 0:
	print(0)
seq = []
for idx in range(n):
	seq.append(int(input().strip()))
last_entry = []
for item in seq:
	idx = bisect_left(last_entry, item)
	if idx == len(last_entry):
		last_entry.append(item)
	else:
		last_entry[idx] = item
print(len(last_entry))


import math

def lisN2(a):
	P = [-1] * len(a)
	M = [-1] * (len(a) + 1)
	L = 0
	for i in range(len(a)):
		lo = 1
		hi = L
		while lo <= hi:
			mid = lo + int((hi - lo + 1) / 2)
			if a[M[mid]] < a[i]:
				lo = mid + 1
			else:
				hi = mid - 1
		l2 = lo
		P[i] = M[l2 - 1]
		M[l2] = i
		L = max(L, l2)
	return L
n = int(input())
A = []
for k in range(n):
	A.append(int(input()))
print(lisN2(A))


n = int(input())
a = []
for i in range(n):
	x = int(input())
	a.append(x)
p = []
p.append(a[0])
ans = 1
for i in range(1, n):
	if a[i] >= p[ans - 1]:
		p.append(a[i])
		ans = ans + 1
	elif p[0] > a[i]:
		p[0] = a[i]
	else:
		l = 0
		r = ans - 1
		while l < r:
			m = l + r >> 1
			if p[m] < a[i]:
				l = m + 1
			else:
				r = m
		p[r] = a[i]
print(ans)


def updateTree(elem, i, tree, arr):
	start = 0
	l = len(tree) - 1
	end = l
	while start <= end:
		middle = (start + end) // 2
		if middle < l and arr[tree[middle + 1]] >= elem and (arr[tree[middle]] < elem):
			tree[middle + 1] = i
			break
		elif arr[tree[middle]] > elem:
			end = middle - 1
		else:
			start = middle + 1
	return

def solve(arr):
	l = 0
	tree = [0]
	for (i, elem) in enumerate(arr[1:]):
		if elem < arr[tree[0]]:
			tree[0] = i + 1
		elif elem > arr[tree[-1]]:
			tree.append(i + 1)
			l += 1
		else:
			updateTree(elem, i + 1, tree, arr)
	return l + 1
n = int(input())
arr = [int(input()) for x in range(n)]
print(solve(arr))


n = int(input())
x = int(input())
t = [x]

def find(x, a, b):
	if a == b:
		return a + 1
	if b - a == 1:
		return b
	else:
		v = (a + b) // 2
		if x >= t[v]:
			return find(x, v, b)
		else:
			return find(x, a, v)
for i in range(n - 1):
	x = int(input())
	if x < t[len(t) - 1] and x > t[0]:
		y = find(x, 0, len(t) - 1)
		if x > t[y - 1] and x < t[y]:
			t[y] = x
	elif x > t[len(t) - 1]:
		t += [x]
	elif x < t[0]:
		t[0] = x
print(len(t))


from bisect import *

def ceilIdx(lis, l, r, val):
	while r > l + 1:
		m = l + (r - l) // 2
		if lis[m] >= val:
			r = m
		else:
			l = m
	return r

def LIS(lis):
	n = len(lis)
	a = [0] * n
	a[0] = lis[0]
	lth = 1
	for i in range(n):
		if lis[i] < a[0]:
			a[0] = lis[i]
		elif lis[i] > a[lth - 1]:
			a[lth] = lis[i]
			lth += 1
		else:
			a[ceilIdx(a, -1, lth - 1, lis[i])] = lis[i]
	return lth

def main():
	n = int(input())
	lis = []
	for i in range(n):
		lis.append(int(input()))
	print(LIS(lis))
main()


def LIS(nums):
	tracker = []
	for n in nums:
		i = binary_search(n, tracker)
		if len(tracker) - i == 1:
			tracker.append(n)
		else:
			tracker[i + 1] = min(tracker[i + 1], n)
	return len(tracker)

def binary_search(needle, haystack):
	(low, high) = (0, len(haystack))
	while high - low > 1:
		k = (high + low) // 2
		if haystack[k] < needle:
			low = k
		else:
			high = k
	return (low, -1)[not haystack or haystack[0] >= needle]
nums = [int(input()) for i in range(int(input()))]
print(LIS(nums))


def findpos(arr, x):
	lo = 0
	hi = len(arr) - 1
	while lo <= hi:
		if x == arr[lo] or x == arr[hi]:
			return -1
		elif x < arr[lo]:
			return lo
		elif x > arr[hi]:
			return hi + 1
		else:
			mid = (hi + lo) // 2
			if x < arr[mid]:
				hi = mid - 1
			elif x > arr[mid]:
				lo = mid + 1
			else:
				return -1
	return -1
n = int(input())
arr = []
lis = [0] * n
for counter in range(n):
	arr.append(int(input()))
sorted_ends = [arr[0]]
num_sorted = [1]
active_array = {1: [arr[0]]}
maxim = 1
for x in arr[1:]:
	if x < sorted_ends[0]:
		if 1 in active_array:
			sorted_ends[0] = x
		else:
			sorted_ends = [x] + sorted_ends
	elif x > sorted_ends[-1]:
		sorted_ends = sorted_ends + [x]
	else:
		pos = findpos(sorted_ends, x)
		if pos != -1:
			sorted_ends[pos] = x
print(len(sorted_ends))


from math import ceil
n = int(input())
X = []
for i in range(n):
	X.append(int(input()))
P = [0] * n
M = [0] * (n + 1)
L = 0
for i in range(0, n):
	lo = 1
	hi = L
	while lo <= hi:
		mid = ceil((lo + hi) / 2)
		if X[M[mid]] < X[i]:
			lo = mid + 1
		else:
			hi = mid - 1
	newL = lo
	P[i] = M[newL - 1]
	M[newL] = i
	if newL > L:
		L = newL
print(L)


def bin_search(first, last, el, array, mins):
	if first == last:
		if el > array[mins[first]]:
			return first + 1
		else:
			return last
	mid = first + int((last - first) / 2)
	if el == array[mins[mid]]:
		return mid
	elif el < array[mins[mid]]:
		temp = bin_search(first, mid, el, array, mins)
	else:
		temp = bin_search(mid + 1, last, el, array, mins)
	return temp

def main():
	n = int(input())
	a = [0] * n
	for i in range(0, n):
		a[i] = int(input())
	mins = [0] * n
	path = [-1] * n
	cur_len = 0
	for i in range(1, n):
		if a[i] > a[mins[cur_len]]:
			mins[cur_len + 1] = i
			path[i] = mins[cur_len]
			cur_len += 1
		else:
			indexie = bin_search(0, cur_len, a[i], a, mins)
			mins[indexie] = i
			path[i] = mins[indexie - 1]
	print(cur_len + 1)
main()


import sys

def find(dp, l, r, key):
	m = 0
	while r - l > 1:
		m = l + (r - l) // 2
		if dp[m] >= key:
			r = m
		else:
			l = m
	return r

def LIS(A, n):
	if n == 0 or len(A) == 0:
		return 0
	dp = []
	dp.append(A[0])
	for i in range(1, n):
		if A[i] > dp[-1]:
			dp.append(A[i])
		elif A[i] < dp[0]:
			dp[0] = A[i]
		else:
			index_of_replacement = find(dp, -1, len(dp) - 1, A[i])
			dp[index_of_replacement] = A[i]
	return len(dp)

def start():
	i = n = 0
	A = []
	for line in sys.stdin:
		if i == 0:
			n = int(line)
			i += 1
		else:
			A.append(int(line))
	print(LIS(A, n))
start()


import sys
import bisect

def main():
	ct = -1
	s = 0
	mmvals = [0]
	for line in sys.stdin:
		v = int(line.rstrip())
		if ct < 0:
			s = v
		elif ct == 0:
			mmvals.append(v)
		else:
			index = bisect.bisect_left(mmvals, v)
			if index < len(mmvals):
				mmvals[index] = v
			else:
				mmvals.append(v)
		ct += 1
	print(len(mmvals) - 1)
main()


from math import ceil
A = [int(input()) for _ in range(int(input()))]
N = len(A)
L = 1
M = [0] + [0 for _ in A]
for i in range(1, N):
	lo = 1
	hi = L
	while lo <= hi:
		mid = ceil((lo + hi) / 2)
		if A[M[mid]] < A[i]:
			lo = mid + 1
		else:
			hi = mid - 1
	M[lo] = i
	if lo > L:
		L = lo
print(L)


def binary_search(arr, begin, end, key):
	while end - begin > 1:
		mid = begin + (end - begin) // 2
		if arr[mid] < key:
			begin = mid
		else:
			end = mid
	return begin

def longest_increasing_sub(arr):
	end_elements = [-1 for i in range(len(arr))]
	end_elements[0] = arr[0]
	max_length = 1
	for i in range(1, len(arr)):
		if arr[i] <= end_elements[0]:
			end_elements[0] = arr[i]
		elif arr[i] > end_elements[max_length - 1]:
			end_elements[max_length] = arr[i]
			max_length += 1
		else:
			replace_index = binary_search(end_elements, 0, max_length - 1, arr[i])
			end_elements[replace_index + 1] = arr[i]
	return max_length
n = int(input())
arr = [int(input()) for i in range(n)]
print(longest_increasing_sub(arr))


from pprint import pformat, pprint
N = int(input())
seq = []
for _ in range(N):
	seq.append(int(input()))

def search(L, M, seq, target):
	low = 1
	high = L
	while low != high:
		mid = int((low + high) / 2 + 1)
		if seq[M[mid]] >= target:
			high = mid - 1
		else:
			low = mid
	return low

def run(seq):
	N = len(seq)
	M = [None] * N
	P = [None] * N
	L = 1
	M[1] = 0
	for l in range(1, N):
		current_index = l
		current = seq[l]
		size_contributed_lis = 1
		index_found = search(L, M, seq, current)
		last_element_of_lis_index = M[index_found]
		last_element_of_lis = seq[M[index_found]]
		if last_element_of_lis < current:
			P[current_index] = last_element_of_lis_index
			size_contributed_lis = index_found + 1
		if M[size_contributed_lis] == None or seq[M[size_contributed_lis]] > current:
			M[size_contributed_lis] = current_index
			if size_contributed_lis > L:
				L = size_contributed_lis
	print(L)
run(seq)


def checks(b, l, r, a):
	while r - l > 1:
		m = l + (r - l) / 2
		m = int(m)
		if b[m] >= a:
			r = m
		else:
			l = m
	return r
n = int(input())
a = [0] * 1000000
for i in range(n):
	a[i] = int(input())
b = [0] * n
len = 1
b[0] = a[0]
for i in range(1, n):
	if a[i] < b[0]:
		b[0] = a[i]
	elif a[i] > b[len - 1]:
		b[len] = a[i]
		len += 1
	else:
		b[checks(b, -1, len - 1, a[i])] = a[i]
print(len)


from math import *
n = int(input())
A = []
for i in range(n):
	A.append(int(input()))
S = [A[0]]

def pos(S, a, low, high):
	if a < S[low]:
		return low
	elif S[high] < a:
		return high
	mid = floor(low / 2 + high / 2)
	if high - low <= 1:
		if S[low] == a:
			return low
		else:
			return high
	elif S[mid] == a:
		ans = mid
	elif a < S[mid]:
		high = mid
		ans = pos(S, a, low, high)
	else:
		low = mid
		ans = pos(S, a, low, high)
	return ans
for a in A[1:]:
	if S[-1] < a:
		S.append(a)
	else:
		pos_a = pos(S, a, 0, len(S) - 1)
		S[pos_a] = a
print(len(S))


import sys

def write(s):
	sys.stderr.write(s)
	pass

def main():
	N = int(sys.stdin.readline())
	seq = [int(line) for line in sys.stdin]
	assert N == len(seq)
	seq2 = [-10 ** 10] + seq + [10 ** 10]
	M = [len(seq2) - 1] * len(seq)
	M[0] = 0
	for i in range(1, len(seq) + 1, 1):
		lo_lis_len = 0
		hi_lis_len = i
		while lo_lis_len < hi_lis_len:
			mi_lis_len = (lo_lis_len + hi_lis_len + 1) // 2
			if seq2[M[mi_lis_len]] < seq2[i]:
				lo_lis_len = mi_lis_len
			else:
				hi_lis_len = mi_lis_len - 1
		assert lo_lis_len == hi_lis_len
		assert M[lo_lis_len] <= i
		if seq2[M[lo_lis_len + 1]] > seq2[i] and seq2[M[lo_lis_len]] < seq2[i]:
			M[lo_lis_len + 1] = i
	for i in range(len(M) - 1, -1, -1):
		if M[i] < len(seq2) - 1:
			print('{}'.format(i))
			return
	raise RuntimeError('Unreachable statement is reached')
main()


from math import ceil
N = int(input().strip())
X = []
for _ in range(N):
	X.append(int(input().strip()))

def longest_increasing_subsequence(X):
	N = len(X)
	P = [0] * N
	M = [0] * (N + 1)
	L = 0
	for i in range(N):
		lo = 1
		hi = L
		while lo <= hi:
			mid = (lo + hi) // 2
			if X[M[mid]] < X[i]:
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		P[i] = M[newL - 1]
		M[newL] = i
		if newL > L:
			L = newL
	S = []
	k = M[L]
	for i in range(L - 1, -1, -1):
		S.append(X[k])
		k = P[k]
	return S[::-1]
print(len(longest_increasing_subsequence(X)))


def findCeil(arr, s, t, key):
	while t - s > 1:
		m = s + (t - s) // 2
		if arr[m] >= key:
			t = m
		else:
			s = m
	return t

def longComSubSeq(arr, size):
	tail = [None] * size
	tail[0] = arr[0]
	pointer = 1
	for i in range(1, size):
		if arr[i] < tail[0]:
			tail[0] = arr[i]
		elif arr[i] > tail[pointer - 1]:
			tail[pointer] = arr[i]
			pointer += 1
		else:
			index = findCeil(tail, -1, pointer - 1, arr[i])
			tail[index] = arr[i]
	return pointer
size = int(input().strip())
arr = []
for _ in range(size):
	arr.append(int(input().strip()))
print(longComSubSeq(arr, size))


import random

def ceilIndex(array, l, r, key):
	while r - l > 1:
		m = int(l + (r - l) / 2)
		if array[m] >= key:
			r = m
		else:
			l = m
	return r

def lis(array, size):
	tailTable = [None] * size
	tailTable[0] = array[0]
	length = 1
	for i in range(1, size):
		if array[i] < tailTable[0]:
			tailTable[0] = array[i]
		elif array[i] > tailTable[length - 1]:
			tailTable[length] = array[i]
			length += 1
		else:
			tailTable[ceilIndex(tailTable, -1, length - 1, array[i])] = array[i]
	return length
n = input()
arr = []
for i in range(0, int(n)):
	element = input()
	arr.append(int(element))
print(lis(arr, int(n)))


from bisect import bisect_left

def lis(seq):
	end = []
	for val in seq:
		idx = bisect_left(end, val)
		if idx == len(end):
			end.append(val)
		else:
			end[idx] = val
	return len(end)
N = int(input())
a = []
for _ in range(N):
	a.append(int(input()))
print(lis(a))


def lengthOfLIS(a):
	l = [None] * len(a)
	l[0] = []
	l[0].append(a[0])
	for i in range(1, len(a)):
		l[i] = []
		for j in range(0, i):
			if a[j] < a[i] and len(l[i]) < len(l[j]):
				l[i] = l[j][:]
		l[i].append(a[i])
	max = 0
	for i in range(len(l)):
		if max < len(l[i]):
			max = len(l[i])
	return max

def ceilIndex(tailIndex, l, r, key):
	while r - l > 1:
		m = int(l + (r - l) / 2)
		if a[m] >= key:
			r = m
		else:
			l = m
	return r

def lengthOfLIS2(a):
	tailTable = [0] * len(a)
	max_len = 1
	tailTable[0] = a[0]
	for i in range(1, len(a)):
		if a[i] < tailTable[0]:
			tailTable[0] = a[i]
		elif a[i] > tailTable[max_len - 1]:
			tailTable[max_len] = a[i]
			max_len += 1
		else:
			tailTable[ceilIndex(tailTable, -1, max_len - 1, a[i])] = a[i]
	return max_len

def lengthOfLIS3(a):
	P = [0] * len(a)
	M = [0] * (len(a) + 1)
	L = 0
	M[0] = 0
	for i in range(0, len(a)):
		lo = 1
		hi = L
		while lo <= hi:
			mid = lo + int((hi - lo) / 2)
			if a[M[mid]] < a[i]:
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		P[i] = M[newL - 1]
		M[newL] = i
		if newL > L:
			L = newL
	return L
n = int(input())
a = [None] * n
for i in range(n):
	a[i] = int(input())
print(lengthOfLIS3(a))


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

def solve2(a, n):
	dp = [1] * (n + 1)
	for i in range(1, n):
		dp[i] = max([dp[j] for j in range(i) if a[j] < a[i]] or [0]) + 1
	return max(dp)

def solve(a, n):
	dp = [0] * (n + 1)
	p = [0] * n
	L = 0
	for i in range(n):
		lo = 1
		hi = L
		while lo <= hi:
			mid = int(lo + (hi - lo) / 2)
			if a[i] > a[dp[mid]]:
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		p[i] = dp[newL - 1]
		dp[newL] = i
		L = newL if newL > L else L
	sol = []
	k = dp[L]
	for i in range(L - 1, -1, -1):
		sol.append(a[k])
		k = p[k]
	return len(sol)
for i in range(n):
	a.append(int(input()))
print(solve(a, n))


def bsearch(a, n, k):
	if k < a[0]:
		return 0
	(left, right, mid) = (0, n - 1, 0)
	while 1:
		mid = (left + right) // 2
		if a[mid] >= k and a[mid - 1] < k:
			break
		if a[mid] >= k:
			right = mid - 1
		else:
			left = mid + 1
	return mid
n = int(input())
a = [0 for i in range(n)]
for i in range(n):
	a[i] = int(input())
dp = [0 for i in range(n)]
count = [0 for i in range(n)]
length = 0
dp[0] = a[0]
count[0] = 1
length = 1
for i in range(1, n):
	if a[i] > dp[length - 1]:
		dp[length] = a[i]
		count[i] = length + 1
		length += 1
	else:
		pos = bsearch(dp, length, a[i])
		dp[pos] = a[i]
		count[i] = pos + 1
print(max(count))


N = int(input())
f = [0] * (N + 1)
res = 0
for i in range(N):
	x = int(input())
	l = 0
	r = res
	while l < r:
		mid = l + r + 1 >> 1
		if f[mid] < x:
			l = mid
		else:
			r = mid - 1
	if f[l + 1] == 0:
		f[l + 1] = x
		res = l + 1
	elif f[l + 1] > x:
		f[l + 1] = x
print(res)


def bisect_left(l, x):
	(lo, hi) = (0, len(l))
	while lo < hi:
		mid = (lo + hi) // 2
		if l[mid] >= x:
			hi = mid
		else:
			lo = mid + 1
	return lo
n = int(input())
a = [int(input()) for i in range(n)]
l = [0 for i in range(n)]
l[0] = a[0]
ilen = 1
for j in a:
	if j < l[0]:
		l[0] = j
	elif j > l[ilen - 1]:
		l[ilen] = j
		ilen += 1
	else:
		l[bisect_left(l[:ilen], j)] = j
print(ilen)


from bisect import bisect_left
l = []
for _ in range(int(input())):
	a = int(input())
	i = bisect_left(l, a)
	if i < len(l):
		l[i] = a
	else:
		l.append(a)
print(len(l))


n = int(input())
l = [None] * n
for i in range(n):
	l[i] = int(input())
h = [None] * (len(l) + 2)
h[1] = l[0]
maxj = 1
for i in range(n):
	if l[i] < h[1]:
		h[1] = l[i]
	if l[i] > h[maxj]:
		maxj += 1
		h[maxj] = l[i]
	else:
		j0 = 1
		j1 = maxj
		while j1 - j0 > 1:
			jj = int((j0 + j1) / 2)
			if h[jj] < l[i]:
				j0 = jj
			else:
				j1 = jj
		if j1 == j0 + 1 and h[j0] < l[i] and (l[i] < h[j1]):
			h[j1] = l[i]
print(maxj)


def lis(X):
	N = len(X)
	P = [0] * N
	M = [0] * (N + 1)
	L = 0
	for i in range(N):
		lo = 1
		hi = L
		while lo <= hi:
			mid = (lo + hi) // 2
			if X[M[mid]] < X[i]:
				lo = mid + 1
			else:
				hi = mid - 1
		newL = lo
		P[i] = M[newL - 1]
		M[newL] = i
		if newL > L:
			L = newL
	S = []
	k = M[L]
	for i in range(L - 1, -1, -1):
		S.append(X[k])
		k = P[k]
	return len(S)
n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
print(lis(a))


import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
d = []
for x in a:
	if not d or x > d[-1]:
		d.append(x)
	else:
		d[bisect.bisect_left(d, x)] = x
print(len(d))


n = int(input().strip())
LIS = []
LIS.append(int(input().strip()))
for i in range(1, n):
	t = int(input().strip())
	if t > LIS[-1]:
		LIS.append(t)
	start = 0
	end = len(LIS) - 1
	while end > start:
		c = int((start + end) / 2)
		if t > LIS[c]:
			start = c + 1
		else:
			end = c
	if t < LIS[start]:
		LIS[start] = t
print(len(LIS))


N = int(input())
M = [0 for i in range(N + 1)]
X = []
for i in range(N):
	X.append(int(input()))

def binarySearch(M, L, i):
	lo = 1
	hi = L
	while lo <= hi:
		mid = int((lo + hi) / 2)
		if X[M[mid]] < X[i]:
			lo = mid + 1
		else:
			hi = mid - 1
	return lo
L = 0
for i in range(N):
	newL = binarySearch(M, L, i)
	M[newL] = i
	L = max(L, newL)
print(L)


from bisect import bisect_left
N = int(input())
A = [int(input()) for _ in range(N)]
tails = [A[0]]
for i in range(1, N):
	if A[i] < tails[0]:
		tails[0] = A[i]
	elif A[i] > tails[-1]:
		tails.append(A[i])
	else:
		j = bisect_left(tails, A[i])
		tails[j] = A[i]
print(len(tails))


from bisect import bisect_left

def longestIS_len_bisect(x):
	len_list = [1]
	end_element = [x[0]]
	for i in x[1:]:
		if i <= end_element[0]:
			if i != end_element[0]:
				if len_list[0] == 1:
					end_element[0] = i
				else:
					end_element.insert(0, i)
					len_list.insert(0, 1)
		elif i > end_element[-1]:
			end_element.append(i)
			len_list.append(len_list[-1] + 1)
		else:
			j = bisect_left(end_element[1:], i)
			if end_element[j + 1] != i:
				if len_list[j + 1] == len_list[j] + 1:
					end_element[j + 1] = i
				else:
					end_element.insert(j + 1, i)
					len_list.insert(j + 1, len_list[j] + 1)
	return len_list[-1]
x = []
for i in range(int(input())):
	x.append(int(input()))
print(longestIS_len_bisect(x))


def find_smallest_elem_as_big_as(sequence, subsequence, elem):
	low = 0
	high = len(subsequence) - 1
	while high > low:
		mid = (high + low) // 2
		if sequence[subsequence[mid]] < sequence[elem]:
			low = mid + 1
		else:
			high = mid
	return high

def dp_increasing(sequence):
	smallest_end_to_subsequence_of_length = []
	parent = [None for _ in sequence]
	for elem in range(len(sequence)):
		if len(smallest_end_to_subsequence_of_length) == 0 or sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]:
			if len(smallest_end_to_subsequence_of_length) > 0:
				parent[elem] = smallest_end_to_subsequence_of_length[-1]
			smallest_end_to_subsequence_of_length.append(elem)
		else:
			location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem)
			smallest_end_to_subsequence_of_length[location_to_replace] = elem
			if location_to_replace != 0:
				parent[elem] = smallest_end_to_subsequence_of_length[location_to_replace - 1]
	curr_parent = smallest_end_to_subsequence_of_length[-1]
	longest_increasing_subsequence = []
	while curr_parent is not None:
		longest_increasing_subsequence.append(sequence[curr_parent])
		curr_parent = parent[curr_parent]
	longest_increasing_subsequence.reverse()
	return longest_increasing_subsequence
n = int(input())
seq = []
for _ in range(n):
	seq.append(int(input()))
print(len(dp_increasing(seq)))


def find_smallest(seq, sub, x):
	low = 0
	high = len(sub) - 1
	while high > low:
		mid = int((high + low) / 2)
		if seq[sub[mid]] < seq[x]:
			low = mid + 1
		else:
			high = mid
	return high

def compute_result(seq):
	small_subseq = []
	parent = [None for _ in seq]
	for x in range(len(seq)):
		if len(small_subseq) == 0 or seq[x] > seq[small_subseq[-1]]:
			if len(small_subseq) > 0:
				parent[x] = small_subseq[-1]
			small_subseq.append(x)
		else:
			position = find_smallest(seq, small_subseq, x)
			small_subseq[position] = x
			if position != 0:
				parent[x] = small_subseq[position - 1]
	current_parent = small_subseq[-1]
	longest_sub = []
	while current_parent is not None:
		longest_sub.append(seq[current_parent])
		current_parent = parent[current_parent]
	return len(longest_sub)
n = int(input())
arr = []
for i in range(n):
	temp = int(input())
	arr.append(temp)
arr = compute_result(arr)
print(arr)


def find(tuple_list, element, start, end):
	while start < end and start + 1 != end:
		middle = (start + end) // 2
		if tuple_list[middle][1] == element:
			return -1
		if tuple_list[middle][1] < element:
			start = middle
		else:
			end = middle
	return start

def replace_or_append(tuple_list, index, element):
	if index + 1 >= len(tuple_list):
		tuple_list.append((tuple_list[index][0] + 1, element))
	else:
		tuple_list[index + 1] = (tuple_list[index][0] + 1, element)

def add_element(active_lists, element):
	if active_lists:
		if active_lists[0][1] < element:
			index = find(active_lists, element, 0, len(active_lists))
			if index == -1:
				return
			replace_or_append(active_lists, index, element)
		else:
			active_lists[0] = (1, element)
	else:
		active_lists.append((1, element))
n = int(input())
A = []
for i in range(n):
	A.append(int(input()))
active_lists = []
for i in range(n):
	add_element(active_lists, A[i])
print(active_lists[-1][0])


import math
import bisect

def LIS(a):
	if len(a) == 0:
		return 0
	mvpl = [0, a[0]]
	with open('debug.out', 'w') as wo:
		for i in range(1, len(a)):
			j = bisect.bisect_right(mvpl, a[i])
			if j == len(mvpl):
				mvpl.append(a[i])
			elif mvpl[j - 1] == a[i]:
				continue
			else:
				mvpl[j] = a[i]
	return len(mvpl) - 1
N = int(input())
seq = [int(input()) for i in range(N)]
print(LIS(seq))


import sys
number = int(next(sys.stdin))
data = [int(x) for x in sys.stdin]
prevs = [-1] * len(data)
mins = [-1] * (len(data) + 1)
maxLen = 0

def findPos(v):
	lo = 1
	hi = maxLen
	while lo <= hi:
		mid = (lo + hi) // 2
		if data[mins[mid]] < v:
			lo = mid + 1
		else:
			hi = mid - 1
	return lo
for i in range(len(data)):
	newPos = findPos(data[i])
	prevs[i] = mins[newPos - 1]
	mins[newPos] = i
	if newPos > maxLen:
		maxLen = newPos
sys.stdout.write(str(maxLen))


import sys, bisect

def ls(seq):
	nums = []
	nums.append(seq[0])
	head = 0
	for x in seq:
		if x <= nums[0]:
			nums[0] = x
		elif x > nums[head]:
			head += 1
			nums.append(x)
		else:
			nums[bisect.bisect_left(nums, x)] = x
	return head + 1
num_input = int(input())
vals = []
for i in range(0, num_input):
	vals.append(int(input()))
max = ls(vals)
print(max)


def BinarySearch(a, tails, l, r, key):
	while r - l > 1:
		m = (l + r) // 2
		if a[tails[m]] >= key:
			r = m
		else:
			l = m
	return r
n = int(input())
a = [int(input())]
tails = [0]
for i in range(1, n):
	x = int(input())
	a.append(x)
	if x < a[tails[0]]:
		tails[0] = i
	elif x > a[tails[-1]]:
		tails.append(i)
	else:
		pos = BinarySearch(a, tails, -1, len(tails) - 1, x)
		tails[pos] = i
print(len(tails))


MAX_ELEM = 100000
n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
m = [MAX_ELEM + 1] * n
result = 0
for elem in a:
	b = 0
	e = n - 1
	biggest_smaller = -1
	while b <= e:
		mid = (b + e) // 2
		if m[mid] < elem:
			b = mid + 1
			biggest_smaller = mid
		else:
			e = mid - 1
	m[biggest_smaller + 1] = elem
	result = max(result, biggest_smaller + 2)
print(result)


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

def binarySearch(nums, target):
	if len(nums) == 0:
		return 0
	(start, end) = (0, len(nums) - 1)
	while start + 1 < end:
		mid = start + (end - start) // 2
		if nums[mid] == target:
			return mid
		elif nums[mid] < target:
			start = mid
		else:
			end = mid
	if nums[start] >= target:
		return start
	if nums[end] >= target:
		return end
	return end + 1
res = []
for num in nums:
	pos = binarySearch(res, num)
	if pos == len(res):
		res.append(num)
	else:
		res[pos] = num
print(len(res))


N = int(input())
A = [int(input()) for t in range(N)]
L = 0
K = [0 for x in range(N + 1)]
P = [0 for x in range(N)]
for i in range(N):
	l = 1
	h = L
	while l <= h:
		m = l + (h - l) // 2
		if A[K[m]] < A[i]:
			l = m + 1
		else:
			h = m - 1
	tempL = l
	P[i] = K[tempL - 1]
	K[tempL] = i
	L = max(tempL, L)
print(L)


def bin_search(lis, x):
	lo = 0
	hi = len(lis) - 1
	while lo < hi:
		mid = int((hi + lo) / 2)
		if lis[mid] >= x:
			hi = mid
		else:
			lo = mid + 1
	return hi
_ = int(input())
(n, lis) = ([], [])
for __ in range(_):
	n.append(int(input()))
for x in n:
	if len(lis) == 0 or lis[len(lis) - 1] < x:
		lis.append(x)
	else:
		s = bin_search(lis, x)
		lis[s] = x
print(len(lis))


import bisect

def algo(a):
	maximal_ends = []
	for it in range(len(a)):
		pos = bisect.bisect_left(maximal_ends, a[it])
		if pos >= len(maximal_ends):
			maximal_ends.append(a[it])
		else:
			maximal_ends[pos] = a[it]
	return len(maximal_ends)
N = int(input())
a = [int(input()) for _ in range(N)]
print(algo(a))


def search(array, num):
	if len(array) == 0:
		return 0
	if array[-1] < num:
		return len(array)
	l = 0
	r = len(array) - 1
	while l < r:
		mid = (l + r) // 2
		if array[mid] < num:
			l = mid + 1
		elif array[mid] > num:
			r = mid
		else:
			return mid
	return l
N = int(input())
array = [0] * N
stack = []
for i in range(N):
	tmp = int(input())
	pos = search(stack, tmp)
	if pos < len(stack):
		stack[pos] = tmp
	else:
		stack.append(tmp)
print(len(stack))


def binarySearch(seqHead, s):
	(lo, hi) = (0, len(seqHead))
	while lo < hi:
		mid = (hi + lo) // 2
		if seqHead[mid] <= s:
			hi = mid
		else:
			lo = mid + 1
	return lo

def longIncSubSeqLogN(S):
	n = len(S)
	seqHead = []
	seqSize = []
	max_so_far = 0
	for s in S:
		if len(seqHead) == 0:
			seqHead.append(s)
			seqSize.append(1)
			max_so_far = max(max_so_far, 1)
		else:
			i = binarySearch(seqHead, s)
			if i == len(seqHead):
				seqHead.append(s)
				seqSize.append(1)
			elif seqHead[i] != s:
				seqHead.insert(i, s)
				seqSize.insert(i, seqSize[i] + 1)
				max_so_far = max(max_so_far, seqSize[i])
			if seqSize[i - 1] == seqSize[i]:
				del seqHead[i - 1]
				del seqSize[i - 1]
	print(max_so_far)
T = int(input())
S = [0] * T
i = 0
while i < T:
	S[i] = int(input())
	i += 1
longIncSubSeqLogN(S)


def binSearch(arr, val, lo, hi):
	if hi == lo:
		if arr[hi] >= val:
			return hi
		else:
			return -1
	else:
		mid = (lo + hi) // 2
		if arr[mid] < val:
			return binSearch(arr, val, mid + 1, hi)
		elif arr[mid] > val:
			return binSearch(arr, val, lo, mid)
		else:
			return mid
a = []
n = int(input().strip())
for i in range(n):
	a.append(int(input().strip()))
s = [a[0]]
for i in range(1, n):
	v = a[i]
	j = binSearch(s, v, 0, len(s) - 1)
	if j < 0:
		s.append(v)
	else:
		s[j] = v
print(len(s))


N = int(input())
A = []
for i in range(N):
	A += [int(input())]
B = [1 for i in range(len(A))]

def find_smallest_elem_as_big_as(sequence, subsequence, elem):
	low = 0
	high = len(subsequence) - 1
	while high > low:
		mid = (high + low) // 2
		if sequence[subsequence[mid]] < sequence[elem]:
			low = mid + 1
		else:
			high = mid
	return high

def optimized_dynamic_programming_solution(sequence):
	smallest_end_to_subsequence_of_length = []
	parent = [None for _ in sequence]
	for elem in range(len(sequence)):
		if len(smallest_end_to_subsequence_of_length) == 0 or sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]:
			if len(smallest_end_to_subsequence_of_length) > 0:
				parent[elem] = smallest_end_to_subsequence_of_length[-1]
			smallest_end_to_subsequence_of_length.append(elem)
		else:
			location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem)
			smallest_end_to_subsequence_of_length[location_to_replace] = elem
			if location_to_replace != 0:
				parent[elem] = smallest_end_to_subsequence_of_length[location_to_replace - 1]
	curr_parent = smallest_end_to_subsequence_of_length[-1]
	longest_increasing_subsequence = []
	while curr_parent is not None:
		longest_increasing_subsequence.append(sequence[curr_parent])
		curr_parent = parent[curr_parent]
	longest_increasing_subsequence.reverse()
	return longest_increasing_subsequence
print(len(optimized_dynamic_programming_solution(A)))


import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
piles = []
for x in a:
	new_pile = [x]
	i = bisect.bisect_left(piles, new_pile)
	if i != len(piles):
		piles[i].insert(0, x)
	else:
		piles.append(new_pile)
print(len(piles))


import math

def upper_bound(last_vals, cur_size, seq_val):
	low = 1
	high = cur_size
	mid = 0
	while high >= low:
		mid = math.ceil((high + low) / 2)
		if last_vals[mid] <= seq_val:
			low = mid + 1
		else:
			high = mid - 1
	return low

def lower_bound(last_vals, cur_size, seq_val):
	low = 1
	high = cur_size
	mid = 0
	while high >= low:
		mid = math.ceil((high + low) / 2)
		if last_vals[mid] >= seq_val:
			high = mid - 1
		else:
			low = mid + 1
	return low

def find_lis(seq, non_decreasing=True):
	seq_length = len(seq)
	last_vals = [0] * (seq_length + 1)
	last_vals[1] = seq[0]
	lis_lengths = [1] * seq_length
	lis_lengths[0] = 1
	cur_size = 1
	for i in range(1, seq_length):
		if seq[i] < last_vals[1]:
			last_vals[1] = seq[i]
		elif seq[i] > last_vals[cur_size]:
			cur_size += 1
			last_vals[cur_size] = seq[i]
			lis_lengths[i] = cur_size
		else:
			replacement_index = upper_bound(last_vals, cur_size, seq[i]) if non_decreasing else lower_bound(last_vals, cur_size, seq[i])
			last_vals[replacement_index] = seq[i]
			lis_lengths[i] = replacement_index
	return last_vals[1:cur_size + 1]
n = int(input())
a = [int(input()) for i in range(n)]
print(len(find_lis(a, False)))


import sys, bisect
list = [0]
n = int(input().strip())
for inputIndex in range(n):
	v = int(input().strip())
	i = bisect.bisect_left(list, v)
	if i == len(list):
		list.append(v)
	else:
		list[i] = v
print(len(list) - 1)


n = int(input())
a = []
l = [0] * n
cur = 1
for i in range(n):
	a += [int(input())]
l[0] = a[0]

def search(i, j, x):
	while i < j:
		m = int((i + j) / 2)
		if x <= l[m]:
			j = m
		else:
			i = m + 1
	return i
for (i, v) in enumerate(a[1:]):
	if v > l[cur - 1]:
		l[cur] = v
		cur += 1
	else:
		l[search(0, cur - 1, v)] = v
print(cur)


def lis(a, n):
	index = 0
	temp = [0] * n
	temp[0] = a[0]
	for i in range(1, n):
		if a[i] > temp[index]:
			index += 1
			temp[index] = a[i]
		elif a[i] < temp[0]:
			temp[0] = a[i]
		else:
			begin = 0
			end = index
			while begin <= end:
				middle = (begin + end) // 2
				if temp[middle] < a[i] and temp[middle + 1] > a[i]:
					temp[middle + 1] = a[i]
				elif temp[middle] < a[i]:
					begin = middle + 1
				else:
					end = middle - 1
	return index + 1
n = int(input())
a = []
for i in range(0, n):
	a.append(int(input()))
result = lis(a, n)
print(result)


import math

def main():
	N = int(input())
	ray_ints = []
	for i in range(N):
		an_int = int(input())
		ray_ints.append(an_int)
	lis = longest_increasing_subsequence(ray_ints)
	print(lis)
	return

def longest_increasing_subsequence(nums):
	num_count = len(nums)
	heritage = []
	increasing_sub = [-1]
	tail_pos = 0
	for i in range(num_count):
		(low, high) = (1, tail_pos)
		while low <= high:
			mid = math.ceil((low + high) / 2)
			if nums[increasing_sub[mid]] < nums[i]:
				low = mid + 1
			else:
				high = mid - 1
		pos = low
		heritage.append(increasing_sub[pos - 1])
		if len(increasing_sub) <= pos:
			increasing_sub.append(0)
		increasing_sub[pos] = i
		tail_pos = pos if pos > tail_pos else tail_pos
	return tail_pos
main()


N = int(input())
A = []
for _ in range(N):
	A.append(int(input()))
sols = {}

def binCeil(e, A, i, j):
	assert e < A[j]
	assert e >= A[i]
	if j - i == 1:
		if A[i] >= e:
			return i
		if A[j] >= e:
			return j
	if i == j:
		return j
	c = (i + j) // 2
	if e == A[c]:
		return c
	if e < A[c]:
		return binCeil(e, A, i, c)
	else:
		return binCeil(e, A, c, j)
for i in range(len(A)):
	if i == 0:
		LCS = [A[0]]
	else:
		if A[i] == LCS[-1]:
			continue
		if A[i] > LCS[-1]:
			LCS.append(A[i])
			sols[A[i]] = LCS[-2]
		elif A[i] <= LCS[0]:
			LCS[0] = A[i]
		else:
			pos = binCeil(A[i], LCS, 0, len(LCS) - 1)
			LCS[pos] = A[i]
			sols[A[i]] = LCS[pos - 1]
head = LCS[-1]
count = 1
print(len(LCS))


import sys

def patiencesort(array, value):
	beg = 0
	end = len(array) - 1
	bucket = None
	while beg != end:
		mid = (beg + end) // 2
		if value <= array[mid]:
			end = mid
		else:
			beg = mid + 1
	bucket = end
	array[bucket] = value
length = int(input())
D = []
for i in range(length):
	temp = int(input())
	D.append(temp)
piles = []
piles.append(D[0])
for i in range(1, length):
	if D[i] > piles[-1]:
		piles.append(D[i])
	else:
		patiencesort(piles, D[i])
print(len(piles))


def bs(a, start, end, x):
	if start < end:
		if start + 1 == end:
			if x > a[start]:
				return start + 1
			else:
				return start
		else:
			mid = int((start + end) / 2)
			if a[mid] > x:
				return bs(a, start, mid, x)
			else:
				return bs(a, mid, end, x)
	else:
		return end

def lis(a, n):
	b = []
	b.append(a[0])
	l = 1
	for i in range(1, n):
		if a[i] < b[0]:
			b[0] = a[i]
		elif a[i] > b[l - 1]:
			b.append(a[i])
			l = l + 1
		else:
			p = bs(b, 0, l - 1, a[i])
			b[p] = a[i]
	print(len(b))
n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
lis(a, n)


def upperIndex(ar, i, j, val):
	while j - i > 1:
		m = i + (j - i) // 2
		if ar[m] >= val:
			j = m
		else:
			i = m
	return j

def LIS_nLgn(ar):
	Tail = len(ar) * [0]
	length = 1
	Tail[0] = ar[0]
	for i in ar[1:]:
		if i < Tail[0]:
			Tail[0] = i
		elif i > Tail[length - 1]:
			Tail[length] = i
			length += 1
		else:
			Tail[upperIndex(Tail, -1, length - 1, i)] = i
	return length
n = int(input())
ar = []
for _ in range(n):
	ar.append(int(input()))
print(LIS_nLgn(ar))


import sys
n = int(input())

class BTreeInterval:

	def __init__(self, n, max):
		self.intervals = [None] * (n + 1)
		self.intervals[0] = (0, max)
		self.current_max = 0
		self.num_max = max

	def get(self, num):
		return self.get1(num, self.current_max / 2, 0, self.current_max)

	def get1(self, num, i, fr, to):
		i = int(i)
		if fr == to:
			return i
		if num >= self.intervals[i][0] and num < self.intervals[i][1]:
			return i
		if num < self.intervals[i][0]:
			return self.get1(num, (fr + i - 1) / 2, fr, i - 1)
		else:
			return self.get1(num, (i + 1 + to) / 2, i + 1, to)

	def set(self, num, i):
		if self.current_max >= i and num >= self.intervals[i][0]:
			return False
		self.intervals[i - 1] = (self.intervals[i - 1][0], num)
		if i > self.current_max:
			self.current_max = i
			self.intervals[i] = (num, self.num_max)
		else:
			self.intervals[i] = (num, self.intervals[i][1])
		return True
nums = []
for _ in range(n):
	nums += [int(input())]
MAX = 100001
cache = [0] * MAX
local_max = 0
max = 1
btree = BTreeInterval(n, MAX)
for i in range(n):
	prev_val = btree.get(nums[i] - 1)
	flag = btree.set(nums[i], prev_val + 1)
	if flag and prev_val + 1 > max:
		max = prev_val + 1
print(max)


def get_max_sub_len_binary(seq, minval):
	max_len = 0
	seq_len = len(seq)
	if seq_len <= 1:
		return seq_len
	ends = list()
	ends.append(minval)
	ends.append(seq[0])
	max_len = 1
	i = 1
	for i in range(1, seq_len):
		elem = seq[i]
		jc = max_len
		jf = 1
		j = 1
		while jc > jf + 4:
			j = jf + (jc - jf) // 2
			if ends[j] > elem:
				jc = j
			elif j == max_len or ends[j + 1] > elem:
				jc = jf = j
			else:
				jf = j
		j = jc
		if j >= max_len:
			j = max_len - 1
		while j >= jf - 1 and elem < ends[j + 1] and (j >= 0):
			j -= 1
		j += 1
		if j == 0:
			j = 1
			ends[1] = elem
		elif elem == ends[j]:
			pass
		elif j == max_len:
			ends.append(elem)
			max_len += 1
		else:
			ends[j + 1] = elem
	return max_len

def do_it():
	n = int(input().strip())
	a = list((int(input().strip()) for i in range(n)))
	print(get_max_sub_len_binary(a, 0))
do_it()


import bisect
N = int(input())
arr = [0] * N
for i in range(N):
	arr[i] = int(input())
seq = []
for i in range(N):
	a = arr[i]
	idx = bisect.bisect_left(seq, a)
	if idx >= len(seq):
		seq.append(a)
	else:
		seq[idx] = a
print(len(seq))