[Solution] Ezzat and Two Subsequences solution codeforces

solution[Solution] Ezzat and Two Subsequences solution codeforces


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

A sequence xx is a subsequence of a sequence yy if xx can be obtained from yy 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][1,5,6] is (1+5+6)/3=12/3=4(1+5+6)/3=12/3=4, so f([1,5,6])=4f([1,5,6])=4.

Input

The first line contains a single integer tt (1t1031≤t≤103)— the number of test cases. Each test case consists of two lines.

The first line contains a single integer nn (2n1052≤n≤105).

The second line contains nn integers a1,a2,,ana1,a2,…,an (109ai109−109≤ai≤109).

It is guaranteed that the sum of nn over all test cases does not exceed 31053⋅105.

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 10610−6.

Formally, let your answer be aa, and the jury’s answer be bb. Your answer is accepted if and only if |ab|max(1,|b|)106|a−b|max(1,|b|)≤10−6.

Example
input

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

Copy
4.500000000
-12.500000000
4.000000000
18.666666667
Note

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

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

Therefore, the maximum possible value 4.54.5.In the second test case, the array is [7,6,6][−7,−6,−6]. These are all the possible ways to split this array:

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

Therefore, the maximum possible value 12.5−12.5.


Solution: Click here

Leave a Comment