Longest Increasing Subsequence

Given an array of integers, determine the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

You are given an array nums of size n. You need to find the maximum length k such that there exists indices \(1 \le i_1 < i_2 < \cdots < i_k \le n\) with \(nums[i_1] < nums[i_2] < \cdots < nums[i_k]\).

Note: The solution should read from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The first line contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single integer representing the length of the longest increasing subsequence in the array.

## sample

8
10 9 2 5 3 7 101 18

4

</p>