Given an array of integers, find the longest increasing subsequence.
A subsequence is just a collection of numbers from the array - however, they must be in order.

For example:
Array: ~1, 2, 5, 4, 3, 6~
The longest increasing subsequence here is ~1, 2, 5, 6~ (or ~1, 2, 4, 6~, or ~1, 2, 3, 6~).
The numbers must be strictly increasing - no two numbers can be equal.

Input Specification

~N \le 5\,000~, the number of integers.
~N~ lines, each with a value in the array.

Output Specification

The length of the longest increasing subsequence of the array.