Given is a sequence of numbers a$1,$ a$2,$ a$3,...,$ an$.$ We want to cross out the smallest number

of elements from this sequence so that the remaining elements are listed in increasing order.

This problem is known as the longest increasing subsequence problem and can be described

formally as follows: We say that aj$1$

$,$ aj$2$

$,...,$ ajk

is a subsequence of the given sequence if and

only if $1<=$ j$1<$ j$2<...<$ jk $<=$ n$.$ A sequence of numbers b$1,$ b$2,...,$ bm is increasing if and

only if b$1<$ b$2<...<$ bm$.$ In the longest increasing subsequence problem we search for an

increasing subsequence of a$1,$ a$2,$ a$3,...,$ an that is the longest possible $($i$.$e$,$ k is as large as

possible$).$

For example, for sequence $8,2,5,7,3,4,9,6,10,$ the longest increasing subsequences are

$2,3,4,6,10$ and $2,5,7,9,10$ either of them is a valid longest increasing subsequence