408494: GYM103150 H William Tell

There are $$$n$$$ stacks of apples, and the $$$i$$$th stack has $$$a_i$$$ apples.

You can shoot an arrow at any nonempty stack. As a result, the number of apples in the stack undergoes one of the following events with equal probability ($$$50\%$$$ chance):

• The number of apples decreases by $$$1$$$, or
• the number of apples becomes $$$0$$$.

Every time you have a choice of which stack to shoot at, you will always shoot at the stack that minimizes the expected value of the total number of arrows you fire. Find the expected value of the number of arrows you fire (until all stacks are empty).

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of stacks of apples.

The next line of each test case contains $$$n$$$ space-separated integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the number of apples in each stack.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

For each test case, output one real number — the expected number of arrows you fire.

Your answer will be considered correct if its absolute or relative error doesn't exceed $$$\mathbf{10^{-4}}$$$. Namely, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, then your answer is accepted if and only if $$$\frac{|a-b|}{\max (1,|b|)} \leq 10^{-4}$$$.

2
4
1 1 1 1
1
2

4.0000
1.5000

In the first test case, no matter which stack you fire at, the resulting number of apples will be $$$0$$$. Therefore, you will always use four arrows.

In the second test case, there is an equal probability of using $$$1$$$ or $$$2$$$ arrows.