Bessie và Elsie phát hiện một hàng gồm \(N\) chiếc bánh (\(2\leq N\leq 5\cdot 10^5\), \(N\) chẵn), có kích thước lần lượt là \(a_1,a_2,\dots,a_N\) theo thứ tự đó (\(1\leq a_i\leq 10^9\)).

Mỗi cô bò đều muốn ăn nhiều nhất có thể. Tuy nhiên, vì là những cô bò rất văn minh, họ quyết định chơi một trò chơi để chia bánh! Hai cô bò luân phiên lượt chơi. Mỗi lượt là một trong hai hành động sau:

1. Bessie chọn hai chiếc bánh kề nhau và xếp chồng chúng, tạo thành một chiếc bánh mới có kích thước bằng tổng kích thước của chúng.
2. Elsie chọn chiếc bánh ngoài cùng bên trái hoặc ngoài cùng bên phải và cất vào phần dự trữ của mình.

Khi chỉ còn một chiếc bánh, Bessie ăn chiếc bánh đó, còn Elsie ăn tất cả bánh trong phần dự trữ. Nếu cả hai chơi tối ưu để tối đa hóa lượng bánh mình ăn và Bessie đi trước, mỗi cô bò sẽ ăn bao nhiêu bánh?

Dữ liệu vào

Mỗi đầu vào gồm \(T\) (\(1\leq T\leq 10\)) bộ test độc lập. Đảm bảo tổng tất cả các giá trị \(N\) trong một đầu vào không vượt quá \(10^6\).

Mỗi bộ test có định dạng như sau. Dòng đầu chứa \(N\). Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách, \(a_1,a_2,\ldots,a_N\).

Dữ liệu ra

Với mỗi bộ test, in một dòng chứa \(b\) và \(e\), lần lượt là lượng bánh Bessie và Elsie sẽ ăn nếu cả hai chơi tối ưu.

Phân nhóm

• Test 2: Tất cả \(a_i\) bằng nhau.
• Test 3: \(N\leq 10\).
• Các test 4–7: \(N\leq 5000\).
• Các test 8–11: Không có ràng buộc bổ sung.

Ví dụ

2
4
40 30 20 10
4
10 20 30 40

60 40
60 40

Nguồn

Đề bài gốc: USACO 2024 December Contest, Silver — Cake Game

Tác giả: Linda Zhao, Agastya Goel, Gavin Ye.