Valar Morghulis

4.5

4 votes
Medium
Problem

Daenerys Targaryen is now targetting the Kingdom of Rock, ruled by House Lannister. Tywin Lannister is a shrewd man and hence sends N dying soldiers to fight Daenerys. The health of each soldier is deteriorating by a particular factor each minute. The initial health of each soldier is 1.00 units. Daenerys uses Rhaegar, the massive dragon for the destroying the army.

Whenever a soldier is killed, it's remaining health can be magically transferred to Daenerys due to the power of the Lord of Light. However, Rhaegar can kill only 1 soldier in 1 minute since he cannot emit fire rapidly. Rhaegar wants to kill the soldiers in such a way that the health gained by Daenerys is maximized.

Your task is to calculate this maximum possible health gain after ALL MEN HAVE DIED.

VALAR MORGHULIS.

Input

The first line contains T, the number of test cases.

The first line of each test case contains a number N, representing the number of soldiers.

The next line contains N space separated real values A_i (upto 2 decimal places only), each indicating the rate of health deterioration of the corresponding soldier.

Output

The only line of output should contain the maximum possible health that Daenerys Targaryen can gain from this battle with an absolute error of atmost 10^-6.

Constraints

1 <= T <= 250

1 <= N <= 100

0 < A_i < 1

Sample Input
2
3
0.5 0.8 0.1
4
0.1 0.2 0.3 0.4
Sample Output
2.140000
1.498000
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In test case 1, Rhaegar can eat soldiers in order 3,1,2 so as to gain (1.0 + 0.5 + (0.8*0.8) = 2.14) which is the maximum possible health gain

Editor Image

?