Ezzat and Two Subsequences

Description:

Input:

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$)— the number of test cases. Each test case consists of two lines.

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot10^5$$$.

Output:

For each test case, print a single value — the maximum value that Ezzat can achieve.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Sample Input:

4
3
3 1 2
3
-7 -6 -6
3
2 2 2
4
17 3 5 -3

Sample Output:

4.500000000
-12.500000000
4.000000000
18.666666667

Note:

In the first test case, the array is $$$[3, 1, 2]$$$. These are all the possible ways to split this array:

• $$$a = [3]$$$, $$$b = [1,2]$$$, so the value of $$$f(a) + f(b) = 3 + 1.5 = 4.5$$$.
• $$$a = [3,1]$$$, $$$b = [2]$$$, so the value of $$$f(a) + f(b) = 2 + 2 = 4$$$.
• $$$a = [3,2]$$$, $$$b = [1]$$$, so the value of $$$f(a) + f(b) = 2.5 + 1 = 3.5$$$.

Therefore, the maximum possible value $$$4.5$$$.

In the second test case, the array is $$$[-7, -6, -6]$$$. These are all the possible ways to split this array:

• $$$a = [-7]$$$, $$$b = [-6,-6]$$$, so the value of $$$f(a) + f(b) = (-7) + (-6) = -13$$$.
• $$$a = [-7,-6]$$$, $$$b = [-6]$$$, so the value of $$$f(a) + f(b) = (-6.5) + (-6) = -12.5$$$.

Therefore, the maximum possible value $$$-12.5$$$.