Беси и Эльза нашли ряд из \(N\) пирожных
\((2 \leq N \leq 5\cdot 10^5, N \text{ четное})\),
с размерами \(a_1,a_2,\dots,a_N\) в таком порядке
(\(1\le a_i\le 10^9\)).
Каждая корова хочет съесть как можно больше. Однако
будучи цивилизованными коровами, они решили сыграть в игру,
чтобы поделить их! В этой игре коровы делают ходы по очереди.
Каждый один из следующих:
- Беси выбирает два соседних пирожных и ставит одно из них на другое,
создавая новое пирожное, размером равным сумме размеров этих пирожных.
- Эльза выбирает либо самое левое пирожное, либо самое правое пирожное
и кладёт себе в тайник.
Когда остаётся только одно пирожное Беси съедает его, а Эльза съедает
все пирожные из своего тайника. Если обе коровы играют оптимально,
и Беси начинает первой, сколько пирожных съест каждая корова?
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Каждый ввод состоит
\(T\) (
\(1\le T\le 10\)) независимых подтестов.
Гарантируется, что сумма всех
\(N\) на вводе не превысит
\(10^6\).
Каждый подтест сформатирован следующим образом. Первая строка содержит \(N\).
Следующая строка содержит \(N\) разделённых одиночными пробелами целых чисел
\(a_1,a_2,\ldots,a_N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите строку, содержащую \(b\) и \(e\), представляющие
количества пирожных, которые съедят Беси и Эльза, если обе коровы играют
оптимально.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
40 30 20 10
4
10 20 30 40
|
60 40
60 40
|