Minimum Groups of Increasing Books

You are given a sequence of n books, where the height of each book is given as an integer. Your task is to partition the books into the minimum number of groups such that in each group the book heights are strictly increasing from left to right.

Formally, given an array of integers \(h_1, h_2, \dots, h_n\), you need to determine the smallest number \(k\) and partition the array into \(k\) subsequences such that for each subsequence \(s = [s_1, s_2, \dots, s_m]\), it holds that \(s_1 < s_2 < \cdots < s_m\).

A greedy approach can be used: iterate over each book and attempt to place it in an existing group (by checking if its height is greater than the last book in that group). If no valid group exists, start a new group.

Note: All formulas are represented in LaTeX format.

inputFormat

The first line contains an integer n representing the number of books. The second line contains n space-separated integers representing the heights of the books.

Example:

5
3 1 4 1 5

outputFormat

Output a single integer representing the minimum number of groups needed so that each group has strictly increasing heights from left to right.

Example:

3

## sample

5
3 1 4 1 5

3

</p>