Longest Increasing Subsequence

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

An increasing subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order, and where every element is strictly greater than its preceding element. Formally, given an array \(A[1\dots n]\), you need to find the maximum length \(L\) such that there exists indices \(1 \le i_1 < i_2 < \dots < i_L \le n\) with \(A[i_1] < A[i_2] < \cdots < A[i_L]\).

For example, given the sequence [5, 3, 4, 8, 6, 7], one valid longest increasing subsequence is [3, 4, 6, 7] and hence the answer is 4.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer \(n\) which represents the number of elements in the sequence.
• The second line contains \(n\) space-separated integers representing the cow jumping heights. If \(n = 0\), the second line will be empty.

outputFormat

Output a single integer to standard output (stdout) — the length of the longest increasing subsequence of the given sequence.

6
5 3 4 8 6 7

4