Longest Increasing Subsequence

You are given a sequence of integers representing the heights of students. Your task is to determine the length of the Longest Increasing Subsequence (LIS) in which every subsequent number is strictly greater than the previous one.

A subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements. Formally, given an array \(A = [a_1, a_2, \ldots, a_n]\), find the maximum \(k\) such that there exists indices \(1 \leq i_1 < i_2 < \ldots < i_k \leq n\) with \(a_{i_1} < a_{i_2} < \ldots < a_{i_k}\).

Input/Output Requirements: The input is read from stdin and the output is written to stdout.

inputFormat

The first line contains an integer \(n\) representing the number of students. The second line contains \(n\) space-separated integers representing the heights of the students.

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

outputFormat

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

6
1 3 5 2 6 4

4