A. Ezzat и две подпоследовательности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У 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$$$) — размер массива Ezzat.

Во второй строке содержится $$$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}$$$.

Пример
Входные данные
4
3
3 1 2
3
-7 -6 -6
3
2 2 2
4
17 3 5 -3
Выходные данные
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$$$.
Таким образом, максимальное значение $$$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$$$.