<?xml version="1.0"?>

-<problem>

<alias>Е</alias>

<name>Интеллектуальное казино</name>


-<limits>

<time>2 секунды</time>

<memory>256 мегабайт</memory>

</limits>


-<statement>

<![CDATA[ <p> В одном иителлектуальном казино распространена необычная игра. В нее играет два игрока. Перед ними выкладывается последовательность из карточек, на которых написаны натуральные числа. Игроки по очереди называют сумму, которую они могут набрать. Тот игрок, который называет большую сумму, назначается играющим. Если он в итоге набирает сумму большую или равную названной, то выигрывает, иначе проигрывает. </p> <p> Очки набираются следующим образом. Все ходы делает играющий. За один ход игрок убирает одну карточку со стола, при этом если у карточки оба первоначальных соседа еще лежат на столе, то игрок получает количество баллов равное среднему арифметическому чисел, написанных на соседних с убираемой карточках. Если у убираемой карточки остался только один сосед (то есть второго соседа либо убрали ранее, либо его не было изначально), то игрок получает количество баллов равное числу, написанному на соседней карточке. А если у убираемой карточки соседей нет, то игрок ничего не получает. Очки полученные за ход прибавляются к общему количеству набранных очков. </p> <p> В этой задаче требуется определить, какое наибольшее суммарное количество баллов можно набрать в этой игре при имеющейся последовательности. </p> ]]>

</statement>


-<input>

<![CDATA[ <p> В первой строке задано число <i>T</i>&nbsp;&mdash; число тестов. Далее идёт описание <i>T</i> тестов. </p> <p> В первой строке теста дано целое число <i>n</i> (1&nbsp;&le;&nbsp;<i>n</i>&nbsp;&le;&nbsp;500&nbsp;000). Во второй строке дана последовательность из <i>n</i> натуральных чисел, написанных на карточках в том порядке, в котором они лежат на столе перед игроками. Числа не превышают 10<sup>9</sup>. </p> <p> Сумма по всем <i>n</i> одного входного файла не превышает&nbsp;500&nbsp;000 . </p> ]]>

</input>


-<output>

<![CDATA[ <p> Для каждого из <i>T</i> тестовых примеров выведите одно число&nbsp;&mdash; ответ на задачу. </p> ]]>

</output>


-<examples>


-<example>

<input> 2 3 3 1 2 4 1 5 3 6 </input>

<output> 4.0 12.0 </output>

</example>

</examples>

</problem>