Hedgemony (Large)

Baron Cohen keeps a hedge of $N$ bushes planted side by side in one straight line. The bushes are numbered 1 to $N$ from left to right, and the height of bush $i$ is an integer. His neighbours trim their hedges so that every bush ends up at the same height. The baron's gardener follows a different rule.

The rule is this. The gardener starts at bush 2 and moves right, visiting bushes $2, 3, \dots, N-1$ in that order. Standing at bush $i$, he takes the average of the current heights of bush $i-1$ and bush $i+1$. If bush $i$ is taller than that average, he cuts its top so that its height becomes exactly the average. If bush $i$ is already at the average or below it, he leaves that bush alone and moves on to the bush on its right. He never walks back, so the height he uses for bush $i-1$ is the height it has after its own trim.

Find the height of bush $N-1$ after the gardener finishes.

The first line contains the number of test cases $T$. Each test case follows on two lines. The first line contains an integer $N$. The second line contains $N$ space-separated integers, the heights of bush 1 through bush $N$.

Limits

• $1 \le T \le 100$
• $3 \le N \le 1000$
• Every height is an integer between 1 and 1000, inclusive.

For each test case, print one line in the form Case #x: y, where $x$ is the case number starting from 1 and $y$ is the height of bush $N-1$ after the gardener has finished. Print $y$ with exactly six digits after the decimal point, rounded to the nearest value that six digits can express. No input is given whose answer lies exactly halfway between two such values.