Read problems statements in Russian also. 
Chef plays with the sequence of N numbers. During a single move Chef is able to choose a non-decreasing subsequence of the sequence and to remove it from the sequence. Help him to remove all the numbers in the minimal number of moves. 

------ Input ------ 

The first line of each test case contains a single N denoting the number of integers in the given sequence. The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the given sequence

------ Output ------ 

Output a single line containing the minimal number of moves required to remove all the numbers from the sequence.

------ Constraints ------ 

$1 ≤ N ≤ 100000.$
$1 ≤ A_{i} ≤ 100000.$
 
------ Scoring ------ 

Subtask 1 (10 points):   N = 10   

Subtask 2 (40 points):   N = 2000   

Subtask 2 (50 points):   N = 100000   

----- Sample Input 1 ------ 
3 
1 2 3
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 

----- Sample Input 2 ------ 
4
4 1 2 3
----- Sample Output 2 ------ 
2
----- explanation 2 ------

Source: codechef | Difficulty: HARD
Tags: Dynamic programming

Combinatorics

Mathematics

Greedy algorithms


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

def lds(A, size):
	tailTable = [0 for i in range(size + 1)]
	len = 0
	tailTable[0] = A[0]
	len = 1
	for i in range(1, size):
		if A[i] < tailTable[0]:
			tailTable[0] = A[i]
		elif A[i] > tailTable[len - 1]:
			tailTable[len] = A[i]
			len += 1
		else:
			tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i]
	return len
t = 1
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().strip().split()))[:n]
	for i in range(n):
		arr[i] *= -1
	print(lds(arr, n))


n = int(input())
arr = list(map(int, input().split()))
lds = []
for i in arr:
	(lo, hi) = (0, len(lds))
	while lo < hi:
		mid = lo + hi >> 1
		if i < lds[mid]:
			lo = mid + 1
		else:
			hi = mid
	if lo == len(lds):
		lds.append(i)
	else:
		lds[lo] = i
print(len(lds))