Longest Increasing Subsequence

This problem requires you to find the length of the longest strictly increasing subsequence in a given sequence of integers. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. In other words, given a sequence \(a_1, a_2, \ldots, a_n\), you need to find the maximum integer \(k\) such that there exists indices \(1 \leq i_1 < i_2 < \cdots < i_k \leq n\) with \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\).

An efficient solution uses dynamic programming with binary search to achieve a time complexity of \(O(n \log n)\), where \(n\) is the length of the sequence.

inputFormat

The input is read from the standard input and begins with an integer \(T\) denoting the number of test cases. Each test case consists of two lines:

• The first line contains an integer \(n\) representing the length of the sequence.
• The second line contains \(n\) space-separated integers representing the sequence.

outputFormat

For each test case, output a single integer on a new line, which is the length of the longest strictly increasing subsequence of the given sequence.

3
5
1 2 1 5 3
4
9 4 7 2
6
2 2 2 2 2 2

3
2
1