Longest Promotion Sequence

You are given a list of employees and their years of experience. An employee can be promoted if they have strictly more years of experience than a previously promoted employee. Your task is to find the length of the longest sequence of promotions possible.

Formally, given an integer \(n\) and an array \(\text{experiences}\) of length \(n\), find the length of the longest increasing subsequence in \(\text{experiences}\). This subsequence represents the maximum sequence of promotions, where each subsequent employee has more years of experience than the previous one.

Example:

Input: n = 6, experiences = [1, 3, 2, 5, 4, 7]
Output: 4

In the above example, one valid longest promotion sequence is: 1, 3, 5, 7.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) representing the number of employees.
2. The second line contains \(n\) space-separated integers where the \(i\)-th integer denotes the years of experience of the \(i\)-th employee.

outputFormat

Output a single integer representing the length of the longest sequence of promotions (i.e., the length of the longest increasing subsequence of the given experience values).

6
1 3 2 5 4 7

4