Longest Increasing Subsequence

Given a sequence of n integers, your task is to find the length of the longest strictly increasing subsequence (LIS) in the sequence. A subsequence is derived by deleting zero or more elements without changing the order of the remaining elements. Formally, if the sequence is represented as \(a_1, a_2, \dots, a_n\), you need to find the maximum length \(L\) for which there exists indices \(1 \leq i_1 < i_2 < \dots < i_L \leq n\) such that \(a_{i_1} < a_{i_2} < \dots < a_{i_L}\).

Example:
For the array [10, 9, 2, 5, 3, 7, 101, 18], one of the longest increasing subsequences is [2, 3, 7, 101], so the answer is 4.

inputFormat

The first line contains a single integer n which denotes the number of elements in the sequence. The second line contains n space-separated integers representing the elements of the sequence. Note that n can be zero, indicating an empty sequence.

outputFormat

Output a single integer which is the length of the longest strictly increasing subsequence.

8
10 9 2 5 3 7 101 18

4