Longest Increasing Subsequence of Hat Numbers

Given a sequence of hat numbers, determine the maximum number of people that can be selected such that each successive person in the sequence has a strictly greater hat number than the previous one. This problem is equivalent to finding the length of the Longest Increasing Subsequence (LIS) in the given array.

Formally, given a sequence \(a_1, a_2, \ldots, a_n\), you are required to find the largest integer \(L\) for which there exists indices \(1 \le i_1 < i_2 < \cdots < i_L \le n\) such that \(a_{i_1} < a_{i_2} < \cdots < a_{i_L}\). The expected solution uses a dynamic programming approach with a time complexity of \(O(n^2)\).

inputFormat

The first line of input contains an integer (n) representing the number of people. The second line contains (n) space-separated integers which denote the hat numbers.

outputFormat

Output a single integer: the length of the longest increasing subsequence in the array of hat numbers.## sample

5
1 3 2 5 4

3