Longest Increasing Subsequence

Given an array of integers, your task is to compute the length of the Longest Increasing Subsequence (LIS) in the array.

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. For an array \(a = [a_1, a_2, \ldots, a_n]\), an increasing subsequence is a sequence \([a_{i_1}, a_{i_2}, \ldots, a_{i_k}]\) such that \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\). The goal is to find the maximum possible \(k\).

Note: The input size can be zero, in which case the output should be 0.

inputFormat

The input is given via stdin in the following format:

• The first line contains a single integer \(n\) (\(0 \le n \le 10^5\)) representing the number of elements in the array.
• The second line contains \(n\) space-separated integers.

outputFormat

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

8
10 9 2 5 3 7 101 18

4