Longest Increasing Subsequence

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

An increasing subsequence is a subset of the sequence where the elements are in strictly increasing order, not necessarily contiguous in the original sequence. More formally, given a sequence \(a_1, a_2, \dots, a_n\), find the maximum length \(L\) such that there exist indices \(1 \le i_1 < i_2 < \dots < i_L \le n\) with \(a_{i_1} < a_{i_2} < \dots < a_{i_L}\).

Input: The first line contains an integer \(n\) (the number of elements). The second line contains \(n\) space-separated integers.

Output: Output a single integer, the length of the longest increasing subsequence.

Note: If \(n = 0\), output 0.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\), the number of elements in the sequence.
• The second line contains \(n\) space-separated integers representing the sequence.

If \(n = 0\), the second line will be absent.

outputFormat

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

## sample

6
10 22 9 33 21 50

4