{"code":"hgtrchiaday","name":"Chia dãy (HSG10v2-2022)","description":"Bạn được giao nhiệm vụ như sau: Cho một dãy số $A$ bao gồm $N$ số nguyên, yêu cầu hãy\r\nchia dãy số trên thành hai phần liên tiếp sao cho tổng các số ở phần bên trái bằng tổng các\r\nsố ở phần bên phải. Với mỗi lần như vậy bạn sẽ được 1 điểm, còn nếu không thể chia được\r\nthì nhiệm vụ sẽ kết thúc. Sau khi chia thành công, bạn sẽ tiếp tục được chọn dãy số bên trái\r\nhoặc bên phải để tiếp tục nhiệm vụ với các bước như trên cho đến khi kết thúc. Hãy tính\r\nxem số điểm lớn nhất bạn có thể đạt được là bao nhiêu?\r\n\r\n

Input

\r\n\r\nĐọc từ file văn bản CHIADAY.INP:\r\n- Dòng đầu tiên ghi một số nguyên $T (1 \\le T \\le 10)$ là số lượng bộ dữ liệu. Mỗi\r\nbộ liệu bao gồm hai dòng:\r\n- Dòng đầu tiên ghi một số nguyên $N$ là số lượng phần tử của dãy $A$.\r\n- Dòng thứ hai gồm Nphần tử của dãy $A$ được ghi cách nhau bởi dấu cách $(0 \\le a_i \\le 10^9)$.\r\n\r\n

Output

\r\n\r\nGhi ra file văn bản CHIADAY.OUT\r\n- Với mỗi bộ dữ liệu in ra một số nguyên trên một dòng là kết quả của bộ dữ liệu đó.\r\n\r\n

Scoring

\r\n\r\n- Subtask $1$ ($30\\%$ số điểm): $N \\le 200$.\r\n- Subtask $2$ ($60\\%$ số điểm): $N \\le 2000$.\r\n- Subtask $3$ ($10\\%$ số điểm): $N \\le 20000$.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3\r\n 3\r\n 3 3 3\r\n 4\r\n 2 2 2 2\r\n 7\r\n 4 1 0 1 1 0 1\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 0\r\n 2\r\n 3\r\n ```","points":300.0,"partial":true,"time_limit":3.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}