Longest Increasing Subsequence

For a given array with N elements, you need to find the length of the longest subsequence from the array such that all the elements of the subsequence are sorted in strictly increasing order.

Strictly Increasing Sequence is when each term in the sequence is larger than the preceding term.

For example:

[1, 2, 3, 4] is a strictly increasing array, while [2, 1, 4, 3] is not.

Input format:

The first line of input contains an integer 'N', representing the size of the array.

The second line of input contains 'N' space-separated integers, representing the elements of the array.

Output Format:

The only output line contains one integer representing the length of the longest increasing subsequence.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given functions.

Input Constraints

1 <= N <= 10^5
-10^5 <= element <= 10^5

Time Limit: 1sec

Sample Input :

6
5 4 11 1 16 8

Sample Output 1 :

3

Explanation of Sample Input 1:

Length of longest subsequence is 3 i.e. [5, 11, 16] or [4, 11, 16].

Sample Input 2:

3
1 2 2

Sample Output 2 :

2