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$$$。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印一个值 - Ezzat 可以实现的最大值。
如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。
示例
输入 #1
4 3 3 1 2 3 -7 -6 -6 3 2 2 2 4 17 3 5 -3
输出 #1
4.500000000 -12.500000000 4.000000000 18.666666667
注意
在第一个测试用例中,数组是 $$$[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$$$ 的值。
在第二个测试用例中,数组为 $$$[-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$$$ 的值。