29128번 - Поход в казино 다국어

В одном иителлектуальном казино распространена необычная игра. В нее играют два игрока. Перед ними выкладывается последовательность из карточек, на которых написаны натуральные числа. Игроки по очереди называют сумму, которую они могут набрать. Тот игрок, который называет большую сумму, назначается играющим. Если он в итоге набирает сумму большую или равную названной, то выигрывает, иначе проигрывает. Конечно же Фома и Псих не могли пройти мимо новой забавы, поэтому решили разобраться в правилах и поиграть.

Выяснилось, что очки набираются следующим образом: Все ходы делает играющий. За один ход игрок убирает одну карточку со стола, при этом если у карточки оба первоначальных соседа еще лежат на столе, то игрок получает количество баллов равное среднему арифметическому чисел, написанных на соседних с убираемой карточках. Если у убираемой карточки остался только один сосед (то есть второго соседа либо убрали ранее, либо его не было изначально), то игрок получает количество баллов равное числу, написанному на соседней карточке. А если у убираемой карточки соседей нет, то игрок ничего не получает. Очки, полученные за ход, прибавляются к общему количеству набранных очков.

Фома и Псих хотят понять, какое наибольшее суммарное количество баллов они могут набрать, если знают все карточки, которые лежат на столе. На решение этой задачи они не хотят тратить время, поэтому просят вас написать программу, которая это вычислит.

В первой строке задано число $T$ --- число тестов. Далее идет описание $T$ тестов. В первой строке теста дано целое число $n$ ($1 \le n \le 500000$). Во второй строке дана последовательность из $n$ натуральных чисел, написанных на карточках в том порядке, в котором они лежат на столе перед игроками. Числа не превышают $10^9$.

Сумма по всем $n$ одного входного файла не превышает 500000.

Для каждого из $T$ тестовых примеров выведите одно число --- ответ на задачу.