Minimum Increasing Subsequences Partition

You are given a sequence of integers. Your task is to partition the sequence into the minimum number of subsequences such that each subsequence is strictly increasing. Every element of the sequence must appear in exactly one subsequence.

For a sequence \( S = [a_1, a_2, \dots, a_n] \), we need to find the smallest integer \( k \) along with subsequences \( S_1, S_2, \dots, S_k \) such that each \( S_i \) is strictly increasing and the union of all \( S_i \) is the original sequence \( S \). The goal is to minimize \( k \).

Example:

Input:  5
        2 1 4 3 5
Output: 2

inputFormat

The first line of input contains an integer \( n \) denoting the number of elements in the sequence. The second line contains \( n \) space-separated integers representing the sequence \( S \).

outputFormat

Output a single integer representing the minimum number of strictly increasing subsequences that the sequence can be partitioned into.

5
2 1 4 3 5

2