PRJAN15D - Prisoners

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 bi set on his head. The controller (Head Chief) 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 head chief 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

Input starts with an integer T, denoting the number of test cases.

Each test case starts with an integer N 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 ith integer is bi denoting the bounty of the ith prisoner.

Output

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

Constraints

  • 0 ≤ T ≤ 100
  • 0 ≤ bi ≤ 103
  • 1 ≤ N ≤ 105

Example

Input:
3
1
10
3
1 2 3
9
200 933 100 6 20 103 310 1 143

Output:
10.000000000000000
2.0000000000000000
201.77777777777780

Explanation

Explanation for first test case: There is only one prisoner. So the expected value will be 1*10 = 10.

Explanation for second test case: There are three prisoners. On the first game any pair can die out of three possible pairs (1-2), (1-3), (2-3). So the expected value will be (1/3)*1 + (1/3)*2 + (1/3)*3 = 2.

Problem-setter: Imtiaz Shakil Siddique


Added by:Shafaet
Date:2015-01-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Progrkriya Contest January 2015

hide comments
2015-01-31 21:33:57 Vamsi Krishna Avula
I am curious how some users got AC before the rejudge(obviously problem wasn't judged by the correct judge)
also I think this is a tutorial problem

Reply: It is moved to Tutorial. And Yes there was a problem regarding judge, Judge was not selected as requirement of the problem.

Last edit: 2015-01-31 21:35:14
2015-01-31 21:33:57 wisfaq
It seems that something has been changed and a rejudge has been done.
As a consequence all comments were deleted.
@psetter: please make a comment when you changed something and did a rejudge.

Reply: Rejudge was done, the problem is moved to tutorial. Sorry for inconvenience.

Last edit: 2015-01-31 21:36:02
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.