카지노 원정

시간 제한2초메모리 제한1024 MB

요약

카드를 한 장씩 제거할 때 양쪽 이웃의 평균 또는 남은 한쪽 이웃의 값을 얻습니다. 모든 제거 순서 중 얻을 수 있는 최대 점수를 구합니다.

난이도: 보통10점 중 6점
유형: 그리디, 연결 리스트, 정렬
정답자: 아직 제출이 없습니다

문제

두 명의 플레이어가 특이한 카지노 게임을 한다. 탁자에는 자연수가 적힌 카드들이 일렬로 놓여 있다. 두 플레이어는 번갈아 가며 자신이 얻을 수 있는 합을 부른다. 더 큰 합을 부른 플레이어가 카드를 제거하는 쪽이 된다. 이 플레이어가 최종적으로 얻은 점수가 부른 합 이상이면 이기고, 그렇지 않으면 진다.

매 차례마다 카드를 한 장 탁자에서 제거한다. 제거하는 카드의 원래 양옆 이웃 카드가 모두 아직 탁자에 있다면, 두 이웃 카드에 적힌 수의 산술 평균을 점수로 얻는다. 이웃 중 하나만 남아 있다면(다른 쪽은 이미 제거되었거나 원래 없었던 경우), 남아 있는 이웃 카드에 적힌 수를 점수로 얻는다. 이웃이 아예 없으면 아무 점수도 얻지 못한다. 한 차례에서 얻은 점수는 누적된다.

포마와 프시흐는 탁자 위의 카드를 모두 알고 있다. 두 사람이 얻을 수 있는 누적 점수의 최댓값을 구하라.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트의 첫 줄에는 정수 $n$ ( $1 \le n \le 500000$ )이 주어진다. 둘째 줄에는 탁자에 놓인 순서대로 카드에 적힌 자연수 $n$ 개가 주어진다. 각 수는 $10^9$ 를 넘지 않는다. 한 입력 파일에 있는 모든 테스트의 $n$ 을 합하면 500000을 넘지 않는다.

출력

$T$ 개의 테스트 각각에 대해 답 하나를 출력한다.

예제1

예제 1
입력
```
2
3
3 1 2
4
1 5 3 6
```
예상 출력
```
4.0
14.0
```