Longest Increasing Subsequence with Maximum Sum

You are given an array of integers. Your task is to find the length of the longest strictly increasing subsequence and the maximum possible sum of such a subsequence.

Let \(A = [a_1, a_2, \dots, a_n]\) be the input array. A subsequence \(S\) of \(A\) is called increasing if for every \(i < j\), \(S_i < S_j\). Your goal is to determine the pair \((L, S)\), where \(L\) is the maximum length of an increasing subsequence and \(S\) is the maximum sum among all increasing subsequences of length \(L\).

You will be provided with multiple test cases. The first line of input contains the number of test cases \(T\). For each test case, the first line contains an integer \(n\) (the number of elements in the array) followed by a line with \(n\) space-separated integers.

Output one line per test case, containing two integers: the length \(L\) and the sum \(S\) of the longest increasing subsequence as described above.

inputFormat

The input is read from stdin and has the following format:

T
n1
a1 a2 ... an1
n2
a1 a2 ... an2
...
nT
a1 a2 ... anT

Where T is the number of test cases. For each test case, the first integer is the number of elements, n, followed by a line with n integers.

outputFormat

For each test case, output a single line to stdout containing two space-separated integers: the length of the longest increasing subsequence and the maximum sum of such a subsequence.

## sample

3
5
5 2 7 4 3
6
1 3 2 4 5 6
4
10 20 30 40

2 12
5 19
4 100

</p>