Limits 1s, 512 MB

Let me tell you a story of a dangerous prison.

There were N prisoners in that prison. It is guaranteed that N is odd. Now each prisoner had a bounty bib_i set on his head. The warden of the prison was a very bad guy. He along with some of his friends (The Mafia Lords) had an idea of playing a game with the lives of the prisoners!

The game was simple; each day randomly two prisoners will be selected (who are alive!) and they will have to fight each other. They must fight until one dies and the sad part is the winning prisoner is also killed by the prison guards as the prison lords don’t want to see the same person fighting another day!

The game ends when there will be exactly one prisoner who will be left alive. The warden of the prison will set him free and will also give him money equivalent to his bounty as a reward. Now suppose you are one of the prisoners (Ahh sad for you) who wants to know what will be the expected bounty of the prisoner who will be alive at last i.e. when the game ends.


Input starts with an integer TT (0T1000 ≤ T ≤ 100), denoting the number of test cases.

Each case starts with an integer NN (1N1051 ≤ N ≤ 10^5) which denotes the number of prisoners initially present in the prison. It is guaranteed that n will always be odd. In the next line there will be N space separated integers, where the ii-th integer is bib_i (0bi1030 ≤ b_i ≤ 10^3) denoting the bounty of the ii-th prisoner.


For each case, print the expected bounty of the alive prisoner (when the game ends). Errors less than 10610^{-6} will be ignored.


1 2 3
200 933 100 6 20 103 310 1 143

For the first test case in sample, there is only one prisoner. So the expected value will be 1×10=101 × 10 = 10.

For the second test case in sample, there are three prisoners. On the first game any pair can die out of three possible pairs (12)(1-2), (13)(1-3), (23)(2-3). So the expected value will be (1/3)×1+(1/3)×2+(1/3)×3=2(1/3) × 1 + (1/3) × 2 + (1/3) × 3 = 2.


Login to submit.



90% Solution Ratio
daryanZEarliest, Aug '15
Imran02Fastest, 0.0s
Tanim018Lightest, 0 B
white_monsterShortest, 79B
Toph uses cookies. By continuing you agree to our Cookie Policy.