Nested Boxes

You are given a set of boxes with different heights. One box can be nested inside another only if its height is strictly less than the other box's height. The task is to determine the maximum number of boxes that can be nested into one another.

This problem is equivalent to finding the Longest Increasing Subsequence (LIS) of the given sequence of heights. Formally, if the input heights are \(a_1, a_2, \ldots, a_n\), you need to find the longest sequence \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) such that \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\) and \(1 \le i_1 < i_2 < \cdots < i_k \le n\).

The optimal solution runs in \(O(n \log n)\) time using a greedy strategy combined with binary search.

inputFormat

The input is read from standard input and consists of two lines.

• The first line contains a single integer \(n\) representing the number of boxes.
• The second line contains \(n\) space-separated integers. Each integer represents the height of a box.

outputFormat

Output a single integer on a line by itself which indicates the maximum number of boxes that can be nested.

## sample

6
1 3 2 4 6 5

4

</p>