Ba phần của mảng

Cho mảng $d_1,d_2,\dots ,d_n$ gồm $n$ số nguyên dương.

Hãy chia mảng thành ba phần (một số phần có thể rỗng) sao cho mỗi phần là một đoạn liên tiếp của mảng ban đầu và mỗi phần tử thuộc đúng một phần. Nói cách khác, nếu phần thứ nhất có $a$ phần tử, phần thứ hai có $b$ phần tử và phần thứ ba có $c$ phần tử ($a+b+c=n$, $a,b,c\ge 0$) thì:

$$su{m}_1=\sum _{1\le i\le a}{d}_i,su{m}_2=\sum _{a+1\le i\le a+b}{d}_i,su{m}_3=\sum _{a+b+1\le i\le n}{d}_i.$$

Tổng của một đoạn rỗng bằng $0$.

Trong tất cả các cách chia thỏa mãn $su{m}_1=su{m}_3$, hãy tìm giá trị $su{m}_1$ lớn nhất.

Luôn tồn tại ít nhất một cách chia hợp lệ: chọn $a=c=0$ và $b=n$, khi đó $su{m}_1=su{m}_3=0$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số phần tử của mảng.
• Dòng thứ hai chứa $n$ số nguyên $d_1,d_2,\dots ,d_n$.

Dữ liệu ra

Một số nguyên duy nhất là giá trị $su{m}_1$ lớn nhất có thể, với điều kiện $su{m}_1=su{m}_3$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le d_i\le {10}^9$

Ví dụ