케이크 게임

Bessie와 Elsie는 한 줄로 놓인 $N$개의 케이크를 발견했다($2 \leq N \leq 5\cdot 10^5$, $N$은 짝수). 왼쪽부터 순서대로 케이크의 크기는 $a_1,a_2,\dots,a_N$이며, $1\le a_i\le 10^9$이다.

두 소는 최대한 많이 먹고 싶어 한다. 그래서 번갈아 턴을 진행하는 게임으로 케이크를 나눈다. 한 턴에는 다음 중 하나를 한다.

1. Bessie는 인접한 두 케이크를 골라 합친다. 두 케이크 크기의 합을 가진 새 케이크가 생긴다.
2. Elsie는 가장 왼쪽 또는 가장 오른쪽 케이크를 골라 자신의 창고에 넣는다.

케이크가 하나만 남으면 Bessie가 그것을 먹고, Elsie는 창고에 있는 케이크를 모두 먹는다. 두 소가 먹는 양을 최대화하도록 최적으로 플레이하고 Bessie가 먼저 시작한다면, 각자 얼마나 먹는가?

입력은 $T$개의 독립적인 테스트 케이스로 이루어진다($1\le T\le 10$). 한 입력에 포함된 모든 $N$의 합은 $10^6$을 넘지 않는다.

각 테스트 케이스는 다음과 같다. 첫 줄에 $N$이 주어진다. 다음 줄에 공백으로 구분된 정수 $a_1,a_2,\ldots,a_N$이 주어진다.

각 테스트 케이스마다 두 소가 최적으로 플레이했을 때 Bessie가 먹는 양 $b$와 Elsie가 먹는 양 $e$를 한 줄에 출력한다.

첫 번째 테스트 케이스에서 최적 플레이는 다음과 같다.

1. Bessie가 가운데 두 케이크를 합친다. 케이크의 크기는 $[40, 50, 10]$이 된다.
2. Elsie가 가장 왼쪽 케이크를 창고에 넣는다. 남은 케이크의 크기는 $[50, 10]$이다.
3. Bessie가 남은 두 케이크를 합친다.

Bessie는 $30+20+10=60$만큼, Elsie는 $40$만큼 먹는다.

두 번째 테스트 케이스는 첫 번째를 뒤집은 것이므로 답이 같다.