Merge Cards

Problem

Panko is playing a game with N cards laid out in a row. The i-th card has the integer Ai written on it.

The game is played in N - 1 rounds. During each round Panko will pick an adjacent pair of cards and merge them. Suppose that the cards have the integers X and Y written on them. To merge two cards, Panko creates a new card with X + Y written on it. He then removes the two original cards from the row and places the new card in their old position. Finally Panko receives X + Y points for the merge. During each round Panko will pick a pair of adjacent cards uniformly at random amongst the set of all available adjacent pairs.

After all N - 1 rounds, Panko's total score is the sum of points he received for each merge. What is the expected value of Panko's total score at the end of the game?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. A second line follows containing N integers, describing the initial row of cards. The i-th integer is Ai.

Output

For each test case, output one line containing x, the expected total score at the end of the game. x will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer.

Limits

Time limit: 1 second.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
1 ≤ Ai ≤ 109 for all i.

Test Set 1

2 ≤ N ≤ 9.

Test Set 2

2 ≤ N ≤ 100.

Test Set 3

2 ≤ N ≤ 1000.

Sample

Input Output
2
3
2 1 10
5
19 3 78 2 31
20.000000
352.333333

In sample case #1, N = 3. The initial row of cards is [2, 1, 10]. In the first round, Panko has two choices, of which he will choose one at random.

  • If Panko merges the first pair (2, 1), then the row of cards becomes [3, 10], adding 2 + 1 = 3 points to his total score. In the second round, there is only one pair remaining (3, 10). If he merges them, the row of cards becomes [13], adding 3 + 10 = 13 points to his total score. Panko ends the game with 3 + 13 = 16 points.
  • If Panko merges the second pair (1, 10), then the row of cards becomes [2, 11], adding 1 + 10 = 11 points to his total score. In the second round, there is only one pair remaining (2, 11). If he merges them, the row of cards becomes [13], adding 2 + 11 = 13 points to his total score.Panko ends the game with 11 + 13 = 24 points.
Thus, the expected number of points Panko ends the game with is (16 + 24)/2 = 20.

In sample case #2, N = 5. The initial row of cards is [19, 3, 78, 2, 31]. There are too many possibilities to list here, so we will only go through one possible game:

  • In the first round, if Panko merges the pair (78, 2), then the row of cards becomes [19, 3, 80, 31], adding 78 + 2 = 80 to his score.
  • In the second round, if Panko merges the pair (80, 31), then the row of cards becomes [19, 3, 111], adding 80 + 31 = 111 to his score.
  • In the third round, if Panko merges the pair (19, 3), then the row of cards becomes [22, 111], adding 19 + 3 = 22 to his score.
  • In the fourth round, if Panko merges the pair (22, 111), then the row of cards becomes [133], adding 22 + 111 = 133 to his score.
At the end of the game explained above, Panko's total score is 80 + 111 + 22 + 133 = 346.


Submitting .cpp to 'Merge Cards'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 3
Your best score: 0
Source: Google Kick Start 2020 Round G

Subtask Score
1 27
2 39
3 34
4 0