You are given an array A of length N.

You have to partition the elements of the array into some [subsequences] such that:
Each element A_{i} (1 ≤ i ≤ N) belongs to exactly one subsequence.
The [mean] of the mean of subsequences is maximised.

Formally, let S_{1}, S_{2}, \dots, S_{K} denote K subsequences of array A such that each element A_{i} (1 ≤ i ≤ N) belongs to exactly one subsequence S_{j} (1 ≤ j ≤ K).  
Let X_{j} (1 ≤ j ≤ K) denote the mean of the elements of subsequence S_{j}. You need to maximise the value \frac{\sum_{j=1}^K X_{j}}{K}.

Print the maximum value. The answer is considered correct if the relative error is less than 10^{-6}.

------ Input Format ------ 

- 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 A_{1}, A_{2}, \ldots, A_{N} - 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}.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$
- Sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2
10 20
3
1 2 3
5
50 50 50 50 50

----- Sample Output 1 ------ 
15
2.25
50

----- explanation 1 ------ 
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 $ = \frac{1+2}{2} = 1.5$.
- Mean of second subsequence $ = \frac{3}{1} = 3$.

Thus, mean of mean of subsequences is $\frac{1.5+3}{2} = \frac{4.5}{2} = 2.25$.

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

Difficulty: HARD
Tags: Mathematics

Starter code:

Solutions:
import math
from statistics import mean
tc = int(input())
while tc > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = sum(a)
	a.sort()
	ans = b / n
	c = 0
	for i in range(n - 1, 0, -1):
		b -= a[i]
		c += a[i]
		ans = max(ans, (c + b / i) / (n - i + 1))
	print(ans)
	tc -= 1


test = int(input())
while test != 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	q = sum(a)
	p = 0
	ans = q / n
	for i in range(n - 1, 0, -1):
		p += a[i]
		q -= a[i]
		ans = max(ans, (q / i + p) / (n - i + 1))
	print(ans)
	test -= 1


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	s = sum(A)
	ans = s / N
	cur = 0
	A.sort()
	for i in range(N - 1, 0, -1):
		cur += A[i]
		s -= A[i]
		ans = max(ans, (cur + s / i) / (N - i + 1))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	sm = sum(a)
	pls = 0
	ans = sm / n
	for i in range(n - 1, 0, -1):
		pls += a[i]
		sm -= a[i]
		ans = max(ans, (sm / i + pls) / (n - i + 1))
	print(ans)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(1, how_much_noob_I_am + 1):
		n = inpu()
		arr = lis()
		arr.sort()
		p = 0
		q = sum(arr)
		ans = q / n
		for i in range(n - 1, 0, -1):
			p += arr[i]
			q -= arr[i]
			ans = max(ans, (q / i + p) / (n - i + 1))
		print(ans)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	total = sum(arr)
	arr.sort()
	mean = total / n
	right = 0
	index = n - 1
	while index > 0:
		total -= arr[index]
		right += arr[index]
		mean = max(mean, (total / index + right) / (n - index + 1))
		index -= 1
	print(mean)


T = int(input())
while T > 0:
	N = int(input())
	A = list(map(int, input().split()))
	tot = sum(A)
	A.sort()
	A.reverse()
	ans = tot / N
	cur = 0
	for k in range(2, N):
		tot -= A[k - 2]
		cur += A[k - 2]
		ans = max(ans, (cur + tot / (N - k + 1)) / k)
	if ans.is_integer():
		print(int(ans))
	else:
		print(ans)
	T -= 1


import sys, os
from sys import stdin, stdout
io_path = 'E:\\Personal\\competitve-programming\\IO'
if os.path.exists(io_path):
	sys.stdout = open(io_path + '/output.txt', 'w')
	sys.stdin = open(io_path + '/input.txt', 'r')

def get_ints():
	return map(int, input().strip().split())

def get_ints_list():
	return list(map(int, input().strip().split()))

def get_string():
	return input().strip()
test_cases = int(input())
while test_cases > 0:
	n = int(input())
	arr = get_ints_list()
	arr.sort()
	total = 0
	for i in arr:
		total += i
	mean = total / n
	index = n - 1
	indv_sum = 0
	while index > 0:
		total -= arr[index]
		indv_sum += arr[index]
		mean = max(mean, (total / index + indv_sum) / (n - index + 1))
		index -= 1
	print('{0:.6f}'.format(mean))
	test_cases -= 1


def cal(l, i, j):
	if i == j:
		return l[i]
	else:
		return (sum(l[i:j]) / (j - i) + l[j]) / 2
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	pre = 0
	ans = 0
	c = 0
	l.sort()
	temp = l.count(l[-1])
	temp1 = temp * l[-1]
	rem = l[:n - temp]
	rem.append(0)
	if n - temp == 0:
		rem = l[-1]
	else:
		rem = sum(rem) / (n - temp)
	ans = (rem + temp1) / (temp + 1)
	sume = sum(l)
	sum1 = 0
	answer = sume / n
	for i in range(n - 1, 0, -1):
		sum1 += l[i]
		sume -= l[i]
		temp = sume / i
		temp += sum1
		temp /= n - i + 1
		answer = max(temp, answer)
	print('{0:.6f}'.format(answer))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	temp = 0
	s = sum(arr)
	t = 0
	ans = 0
	for el in arr:
		temp += el
		t += 1
		ans = max(ans, (temp / t + (s - temp)) / (n - t + 1))
	print(ans)


t = int(input())
for test in range(t):
	n = int(input())
	lks = list(map(int, input().split()))
	lks.sort()
	ss = sum(lks)
	curr = ans = 0
	for i in range(n):
		curr += lks[i]
		ans = max(ans, (ss - curr + curr / (i + 1)) / (n - i))
	print(ans)


t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	s = sum(a)
	c = ss = ans = 0
	for i in range(n):
		ss += a[i]
		s -= a[i]
		c += 1
		ans = max(ans, (s + ss / c) / (n - i))
	print(ans)


test_cases = int(input())
for i in range(test_cases):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	mid = n // 2
	(curr_sum, remainder) = (sum(arr[:mid]), sum(arr[mid:]))
	curr_max = (curr_sum / mid + remainder) / (n - mid + 1)
	for j in range(n // 2 + 1, n):
		curr_sum += arr[j - 1]
		remainder -= arr[j - 1]
		curr = (curr_sum / j + remainder) / (n - j + 1)
		if curr >= curr_max:
			curr_max = curr
		else:
			break
	print(curr_max)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	n = len(arr)
	arr.sort()
	prefixsum = [0] * (n + 1)
	for i in range(1, len(arr) + 1):
		prefixsum[i] = prefixsum[i - 1] + arr[i - 1]
	backwardsum = 0
	res = 0
	for i in range(len(arr) - 1, -1, -1):
		c = (prefixsum[i + 1] / (i + 1) + backwardsum) / (len(arr) - 1 - i + 1)
		res = max(res, c)
		backwardsum += arr[i]
	if int(res) == res:
		print(int(res))
	else:
		print(res)


import sys
from math import sqrt, gcd, factorial, ceil, floor
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	a = L()
	a.sort()
	ans = (sum(a) + a[-1] * (n - 2)) / (2 * (n - 1))
	s = a[-1]
	s2 = sum(a) - a[-1]
	for i in range(n - 2, 0, -1):
		s += a[i]
		s2 -= a[i]
		tans = (s + s2 / i) / (n - i + 1)
		ans = max(ans, tans)
	print('{:.6f}'.format(ans))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	a.sort()
	fin = 1.0 * s / n
	ss1 = 0
	for i in range(n - 1, 0, -1):
		ss1 += a[i]
		s -= a[i]
		ans1 = 1.0 * s / i + ss1
		ans1 = ans1 / (n - i + 1)
		fin = max(fin, ans1)
	print(fin)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	a.sort()
	s = sum(a)
	ss = 0
	c = 0
	for i in range(n):
		ss = ss + a[i]
		c = c + 1
		ans = max(ans, (s - ss + ss / c) / (n - i))
	print(ans)


nn = int(input())
for awd in range(nn):
	n = int(input())
	l = list(map(int, input().split(' ')))
	l.sort()
	vals = []
	start = 0
	for (ind, i) in enumerate(l):
		ind += 1
		start += i
		vals.append(start / ind)
	maxi = 0
	dp = {}
	for i in range(len(l) - 1, len(l) // 2 - 2, -1):
		count = len(l) - i + 1
		total = l[i] + dp.get(i + 1, 0)
		dp[i] = total
		calc = (total + vals[i - 1]) / count
		maxi = max(maxi, calc)
	print(maxi)


for tcase in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	s = [0]
	for ai in a:
		s.append(s[-1] + ai)
	ans = max(((s[n] - s[i] + s[i] / i) / (n - i + 1) for i in range(1, n)))
	print(ans)


from collections import deque
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	A.sort()
	(current_sum, current_len) = (sum(A), len(A))
	mean = current_sum / current_len
	a_q = deque(A)
	combined = 0
	while True:
		item_1 = a_q.popleft()
		item_2 = a_q.popleft()
		current_len -= 1
		combined += 1
		current_sum = current_sum - item_1 - item_2 + (item_1 * combined + item_2) / (combined + 1)
		mean_after = current_sum / current_len
		if mean_after > mean:
			mean = mean_after
			a_q.appendleft((item_1 * combined + item_2) / (combined + 1))
		else:
			print(mean)
			break
		if len(a_q) <= 1:
			print(mean)
			break


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	(psum, sumi) = (0, sum(a))
	(maxi, rm) = (sumi / n, n)
	for (i, v) in enumerate(a, start=1):
		psum += v
		sumi -= v
		maxi = max(maxi, (psum / i + sumi) / rm)
		rm -= 1
	print(maxi)


t = int(input())
while t > 0:
	n = int(input())
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	a.sort()
	s = sum(a)
	ans = s / n
	cur = 0
	for i in range(n - 1):
		cur += a[i]
		avg = (cur / (i + 1) + (s - cur)) / (n - i)
		if avg < ans:
			break
		ans = avg
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	if n == 2:
		print(sum(a) / 2)
		continue
	s = sum(a)
	curr = a[0]
	currn = 1
	currt = s - a[0]
	ms = [s / n]
	for i in a[1:]:
		curr = (curr * currn + i) / (currn + 1)
		currn += 1
		currt = currt - i
		ms.append((currt + curr) / (n - currn + 1))
	print(max(ms))


t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	ar.sort(reverse=True)
	s = sum(ar)
	ans = s / n
	curr_sz = 1
	curr = 0
	for elm in ar:
		if n == curr_sz:
			break
		s -= elm
		curr += elm
		avg = (s / (n - curr_sz) + curr) / (curr_sz + 1)
		curr_sz += 1
		ans = max(ans, avg)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	line = input()
	a = list(map(int, line.split()))
	a.sort(reverse=True)
	total_sum = sum(a)
	avg = total_sum / n
	total_n = 1
	total_avgs = 0
	big_avg = avg
	removed = False
	while len(a) > 0:
		if a[0] > big_avg:
			value = a.pop(0)
			total_sum -= value
			n -= 1
			avg = total_sum / n
			total_avgs += value
			total_n += 1
			temp = big_avg
			big_avg = (avg + total_avgs) / total_n
			if temp > big_avg:
				print(temp)
				removed = True
				break
		else:
			break
	if not removed:
		print(big_avg)


for _ in range(int(input())):
	size = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	presum = [0] * size
	presum[0] = arr[0]
	for i in range(1, size):
		presum[i] = presum[i - 1] + arr[i]
	ans = -1
	for i in range(0, size):
		ans = max(ans, (presum[i] / (i + 1) + presum[size - 1] - presum[i]) / (size - i))
	print(ans)


T = int(input())
for ts in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	A.sort()
	max_av = 0.5 * sum(A[:N - 1]) / (N - 1) + 0.5 * A[N - 1]
	for i in range(3, N):
		av_all = sum(A[:N - i + 1]) / (N - i + 1)
		av = 1 / i * (sum(A[N - i + 1:]) + av_all)
		if max_av > av:
			break
		else:
			max_av = av
	print(max_av)