Casino Trip

Time limit2sMemory limit1024 MB

Summary

Remove cards from a row one at a time, scoring the mean of both neighbors or the one remaining neighbor; find the maximum total score.

Level: Medium6 of 10
Topics: Greedy, Linked list, Sorting
Solved: No attempts yet

Problem

Two players take part in an unusual game at an intellectual casino. A row of cards with natural numbers written on them lies on the table. The players take turns naming a sum they can score. The player who names the larger sum becomes the one who removes the cards. If that player's total at the end is at least the named sum, they win. Otherwise they lose.

On each turn, one card is removed from the table. If both original neighbors of the removed card are still on the table, the player gains the arithmetic mean of the two numbers on those neighbors. If only one neighbor is still on the table (the other was removed earlier or never existed), the player gains the number on that neighbor. If the removed card has no neighbors, the player gains nothing. The points gained on each turn are added to the running total.

Foma and Psykh know all the cards on the table. Find the maximum total score they can gain.

Input

The first line contains the number of tests $T$ . Each test starts with a line containing an integer $n$ ( $1 \le n \le 500000$ ). The next line contains $n$ natural numbers written on the cards, in the order they lie on the table. Each number does not exceed $10^9$ . The sum of $n$ over all tests in one input file does not exceed 500000.

Output

For each of the $T$ tests, print one number: the answer to the problem.

Examples1

Example 1
Input
```
2
3
3 1 2
4
1 5 3 6
```
Expected output
```
4.0
14.0
```