human
Can you solve the below in PYTHON?
Ezzat has an array of n integers (maybe negative). He wants to split it into two non-empty subsequences a and b, such that every element from the array belongs to exactly one subsequence, and the value of f(a) + f(b) is the maximum possible value, where f(x) is the average of the subsequence x. 

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

Input

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

The first line contains a single integer n (2 ≤ n ≤ 10^5).

The second line contains n integers a_1, a_2, …, a_n (-10^9 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 3⋅10^5.

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 10^{-6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-6}.

Example

Input

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

Output

4.500000000
-12.500000000
4.000000000
18.666666667

Note

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

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

Therefore, the maximum possible value 4.5.

In the second test case, the array is [-7, -6, -6]. These are all the possible ways to split this array: 

  * a = [-7], b = [-6,-6], so the value of f(a) + f(b) = (-7) + (-6) = -13. 
  * a = [-7,-6], b = [-6], so the value of f(a) + f(b) = (-6.5) + (-6) =...
 ... Can you provide a Python code to print a single value — the maximum value that Ezzat can achieve?
assistant
#Here is Python code to print a single value — the maximum value that Ezzat can achieve.

import sys
testing = len(sys.argv) == 4 and sys.argv[3] == "myTest"
interactive = False
if testing:
    cmd = sys.stdout
    from time import time
    start_time = int(round(time() * 1000)) 
    readAll = open(sys.argv[1], 'r').read
    sys.stdout = open(sys.argv[2], 'w')
else:
    readAll = sys.stdin.read

# ############ ---- I/O Functions ---- ############

class InputData:
    def __init__(self):
        self.lines = readAll().split('\n')
        self.n = len(self.lines)
        self.ii = -1
    def input(self):
        self.ii += 1
        assert self.ii < self.n
        return self.lines[self.ii]

flush = sys.stdout.flush
if interactive and not testing:
    input = sys.stdin.readline
else:
    inputData = InputData()
    input = inputData.input

def intin():
    return(int(input()))
def intlin():
    return(list(map(int,input().split())))
def chrin():
    return(list(input()))
def strin():
    return input()
def lout(l, sep="\n", toStr=True):
    print(sep.join(map(str, l) if toStr else l))
def dout(*args, **kargs):
    if not testing: return
    if args: print(args[0] if len(args)==1 else args)
    if kargs: print([(k,v) for k,v in kargs.items()])
def ask(q):
    sys.stdout.write(str(q)+'\n')
    flush()
    return intin()
    
# ############ ---- I/O Functions ---- ############

# from math import ceil
# from collections import defaultdict as ddict, Counter
# from heapq import *
# from Queue import Queue

def main():
    n = intin()
    a = intlin()
    return max(a) + (sum(a)-max(a))/(n-1.0)

anss = []
for _ in xrange(intin()):
    anss.append(main())
    # anss.append("YES" if main() else "NO")
lout(anss)

if testing:
    sys.stdout = cmd
    print(int(round(time() * 1000))  - start_time)