**Too Mean solution codechef** – You are given an array A of length N.

## [Solution] Too Mean solution codechef

You have to partition the elements of the array into some subsequences such that:

Each element Ai (1≤i≤N) belongs to exactly one subsequence.

The mean of the mean of subsequences is maximised.

Formally, let S1,S2,…,SK denote K subsequences of array A such that each element Ai (1≤i≤N) belongs to exactly one subsequence Sj (1≤j≤K).

Let Xj (1≤j≤K) denote the mean of the elements of subsequence Sj. You need to maximise the value ∑Kj=1XjK.

Print the maximum value. The answer is considered correct if the relative error is less than 10−6.

## [Solution] Too Mean solution codechef

First line will contain T, number of test cases. Then the test cases follow.

First line of each test case consists of a single integer N – denoting the length of array A.

Second line of each test case consists of N space-separated integers A1,A2,…,AN – denoting the array A.

Output Format

For each test case, output in a single line, the maximum possible mean of mean of subsequences. The answer is considered correct if the relative error is less than 10−6.

## [Solution] Too Mean solution codechef

- 1≤T≤1000
- 2≤N≤105
- 1≤Ai≤106

Sum of N over all test cases does not exceed 3⋅105.

Sample Input 1

3

2

10 20

3

1 2 3

5

50 50 50 50 50

Sample Output 1

15

2.25

50

## Too Mean solution Explanation

Test Case 1: We can partition the array in 2 ways – ({10},{20}) or ({10,20}). In both cases, mean of mean of subsequences comes out to be 15.

Test Case 2: The optimal partition is ({1,2},{3}).

Mean of first subsequence =1+22=1.5.

Mean of second subsequence =31=3.

Thus, mean of mean of subsequences is 1.5+32=4.52=2.25.

Test Case 3: Any partition will yield the mean of mean of subsequences as 50.