Poor Miku#12214
After dealing with her obsessed fans, Miku realizes she wasted a lot of time and now she is late for the concert. She decides to take the bus, but she does not have enough money, so she resorts to gambling. She chooses to play the Plinko balls game, described as follows:
The structure of the game has layers, numbered through .
The first (top) layer has slot,
the second layer has slots,
the -th layer has slots,
the last (bottom) layer has slots with positive integer values a_1, a_2, \dots, a_n.
Miku can drop a ball from any slot in any layer except the last one. If she drops the ball from (l, j) (1 \le l < n, 1 \le j \le l), meaning layer and slot , the ball makes n-l moves until reaching the bottom layer.
At each move, the ball goes left or right with equal probability \tfrac{1}{2}. More formally, if the ball is at (l, j) (1 \le l < n, 1 \le j \le l), it can move either to slot (l+1, j) or (l+1, j+1).
When the ball ends up at (1 \le j \le n), Miku wins a_j coins and the game ends.
Miku needs your help to find the maximum expected number of coins she can win, being able to drop the ball from any slot in any layer except the last one.
Your answer will be considered correct if its absolute error does not exceed 10^{-6}.
The first line contains a single integer (1 \le t \le 1000)—the number of test cases.
The first line of each test case contains a single integer (2 \le n \le 2 \cdot 10^5).
The following line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 2 \cdot 10^5)—the slot values of the last layer.
It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.
The output should consist of lines, each containing one value: the maximum expected number of coins Miku can win.
Example 1
In the first test case, Miku can drop the ball at , where she gets the maximum expected number of coins.
In the second test case: If Miku drops the ball at , it can go:
(ends up at a_1)
(ends up at a_2)
(ends up at a_2)
(ends up at a_3)
( means left and means right).
So the expected number of coins is \frac{a_1+a_2+a_2+a_3}{4} = \frac{12}{4} = 3.
In the third test case, Miku can drop the ball anywhere since all values are equal, and she will win coins.
Subtask ( points): (\sum n \le 10)
Subtask ( points): (\sum n \le 100)
Subtask ( points): (\sum n \le 500)
Subtask ( points): (\sum n \le 1000)
Subtask ( points): (\sum n \le 5000)
Subtask ( points): No additional constraints