Longest Increasing Subsequence Challenge

Given an array of integers, find the longest increasing subsequence (LIS) in the array and output both the subsequence and its length. The longest increasing subsequence is defined as the subsequence where each element is strictly greater than its previous element. Formally, for an array \(a_1, a_2, \dots, a_n\), find a subsequence \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) such that \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\) and \(k\) is maximized.

You may use dynamic programming or a patience sorting based method to solve the problem.

inputFormat

The first line of input contains an integer \(T\), the number of test cases. Each test case consists of two lines:

1. The first line contains an integer \(n\), representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers.

outputFormat

For each test case, output two lines:

1. The first line should contain the longest increasing subsequence as space-separated integers. If the subsequence is empty, output an empty line.
2. The second line should contain the length of this subsequence.

3
8
10 9 2 5 3 7 101 18
6
-1 3 -2 4 -3 5
4
5 5 5 5

2 3 7 18
4
-1 3 4 5
4
5
1