Longest Increasing Subsequence

You are given an array of integers. Your task is to compute the length of the Longest Increasing Subsequence (LIS) in the array.

A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements. Formally, given an array \(a_1, a_2, \dots, a_n\), a subsequence is a sequence \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) where \(1 \le i_1 < i_2 < \cdots < i_k \le n\). The subsequence is increasing if \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\).

Your solution should read the input from standard input (stdin) and write the answer to standard output (stdout).

Example:

Input:
8
10 9 2 5 3 7 101 18
Output:
4

inputFormat

The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Output a single integer representing the length of the longest increasing subsequence.## sample

8
10 9 2 5 3 7 101 18

4