У 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\).
Выходные данные
Для каждого набора входных данных выведите одно число — максимальное значение, которое может получить Ezzat.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит \(10^{-6}\).
Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если и только если \(\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}\).
Примечание
В первом примере массив \([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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|