Taco Trees: Longest Increasing Subsequence

You are given several test cases. In each test case, there is a sequence of tree heights. Your task is to determine the maximum number of trees that can be planted such that their heights form a strictly increasing sequence. This is equivalent to finding the length of the Longest Increasing Subsequence (LIS) for the sequence.

Mathematical Formulation:

For a sequence of heights \(a_1, a_2, \dots, a_n\), find the maximum \(k\) for which there exists indices \(1 \leq i_1 < i_2 < \dots < i_k \leq n\) such that \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\). In other words, determine \(\text{LIS}(a)\).

The solution typically makes use of dynamic programming combined with binary search for an efficient \(O(n \log n)\) implementation.

inputFormat

The first line of input contains a single integer \(T\) denoting the number of test cases. The description of each test case follows:

• The first line contains an integer \(N\) — the number of trees.
• The second line contains \(N\) space-separated integers representing the heights of the trees.

If \(N = 0\), the second line will be empty.

outputFormat

For each test case, output a single line containing a single integer — the length of the longest strictly increasing subsequence of tree heights.

## sample

5
5
3 10 2 1 20
1
5
5
9 8 7 6 5
5
1 2 3 4 5
7
10 22 9 33 21 50 41

3
1
1
5
4

</p>