CF1557A.Ezzat and Two Subsequences

Ezzat has an array of $n$ integers (maybe negative). He wants to split it into two non-empty subsequences $a$ and $b$, such that every element from the array belongs to exactly one subsequence, and the value of $f(a) + f(b)$ is the maximum possible value, where $f(x)$ is the average of the subsequence $x$.

A sequence $x$ is a subsequence of a sequence $y$ if $x$ can be obtained from $y$ by deletion of several (possibly, zero or all) elements.

The average of a subsequence is the sum of the numbers of this subsequence divided by the size of the subsequence.

For example, the average of $[1,5,6]$ is $(1+5+6)/3 = 12/3 = 4$, so $f([1,5,6]) = 4$.

Ezzat 有一个包含 $n$ 个整数（可能为负数）的数组。他希望将该数组划分为两个非空子序列 $a$ 和 $b$，使得数组中的每个元素恰好属于其中一个子序列，且 $f(a) + f(b)$ 的值达到最大可能值，其中 $f(x)$ 表示子序列 $x$ 的平均值。

若序列 $x$ 可通过从序列 $y$ 中删除若干（可能为零个或全部）元素得到，则称 $x$ 是 $y$ 的一个子序列。

子序列的平均值定义为该子序列中所有数字之和除以该子序列的长度。

例如，$[1,5,6]$ 的平均值为 $(1+5+6)/3 = 12/3 = 4$，因此 $f([1,5,6]) = 4$。

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。每个测试用例包含两行。

第一行包含一个整数 $n$（$2 \le n \le 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $3\cdot10^5$。

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}$.

对于每个测试用例，输出一个值——Ezzat 能够达到的最大值。

若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

形式化地，设你的答案为 $a$，评测组的答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，你的答案被接受。

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$.

在第一个测试用例中，数组为 $[3, 1, 2]$。以下是将该数组分割的所有可能方式：

• $a = [3]$，$b = [1,2]$，则 $f(a) + f(b) = 3 + 1.5 = 4.5$。
• $a = [3,1]$，$b = [2]$，则 $f(a) + f(b) = 2 + 2 = 4$。
• $a = [3,2]$，$b = [1]$，则 $f(a) + f(b) = 2.5 + 1 = 3.5$。

因此，最大可能值为 $4.5$。

在第二个测试用例中，数组为 $[-7, -6, -6]$。以下是将该数组分割的所有可能方式：

• $a = [-7]$，$b = [-6,-6]$，则 $f(a) + f(b) = (-7) + (-6) = -13$。
• $a = [-7,-6]$，$b = [-6]$，则 $f(a) + f(b) = (-6.5) + (-6) = -12.5$。

因此，最大可能值为 $-12.5$。