Longest Increasing Subsequence

Given a sequence of integers, your task is to determine the length of the longest strictly increasing subsequence (LIS).

A subsequence is derived from the sequence by deleting some or no elements without changing the order of the remaining elements.

The problem can be formulated as follows:

Given an array \(nums\) of length \(n\), find the length of the longest subsequence such that every element in the subsequence is strictly greater than the previous one. Formally, if the subsequence is \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) then \(a_{i_1} < a_{i_2} < \ldots < a_{i_k}\).

Example: For the input array [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101] and its length is 4.

inputFormat

The input is given from standard input (stdin). The first line contains an integer \(n\) (0 ≤ \(n\) ≤ 10⁵), representing the number of elements in the array. If \(n > 0\), the second line contains \(n\) space-separated integers representing the elements of the array.

If \(n = 0\), no further input is provided.

outputFormat

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

The output should be written to standard output (stdout).

## sample

0

0