C. Три части массива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив $$$d_1, d_2, \dots, d_n$$$, состоящий из $$$n$$$ целых чисел.

Ваша задача — разделить этот массив на три части (некоторые из которых могут быть пустыми) таким образом, что каждый элемент массива принадлежит ровно одной из частей, и каждая часть образует последовательный непрерывный подотрезок (возможно, пустой) изначального массива.

Пусть сумма элементов первой части равна $$$sum_1$$$, сумма элементов второй части равна $$$sum_2$$$ и сумма элементов третьей части равна $$$sum_3$$$. Среди всех возможных разбиений массива вам нужно выбрать такое, что $$$sum_1 = sum_3$$$ и $$$sum_1$$$ является максимально возможной.

Более формально, если первая часть массива содержит $$$a$$$ элементов, вторая часть массива содержит $$$b$$$ элементов и третья часть массива содержит $$$c$$$ элементов, тогда:

$$$$$$sum_1 = \sum\limits_{1 \le i \le a}d_i,$$$$$$ $$$$$$sum_2 = \sum\limits_{a + 1 \le i \le a + b}d_i,$$$$$$ $$$$$$sum_3 = \sum\limits_{a + b + 1 \le i \le a + b + c}d_i.$$$$$$

Сумма пустого массива равна $$$0$$$.

Ваша задача найти такое разбиение массива, что $$$sum_1 = sum_3$$$ и $$$sum_1$$$ является максимально возможной.

Входные данные

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество элементов массива $$$d$$$.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 10^9$$$) — элементы массива $$$d$$$.

Выходные данные

Выведите одно целое число — максимально возможное значение $$$sum_1$$$, удовлетворяющее условию $$$sum_1 = sum_3$$$.

Очевидно, всегда существует хотя бы один способ разбить массив нужным образом (если $$$a=c=0$$$ и $$$b=n$$$).

Примеры
Входные данные
5
1 3 1 1 4
Выходные данные
5
Входные данные
5
1 3 2 1 4
Выходные данные
4
Входные данные
3
4 1 2
Выходные данные
0
Примечание

В первом тестовом примере только одно возможное разбиение, которое максимизирует $$$sum_1$$$: $$$[1, 3, 1], [~], [1, 4]$$$.

Во втором тестовом примере существует единственный способ набрать $$$sum_1=4$$$: $$$[1, 3], [2, 1], [4]$$$.

В третьем тестовом примере есть только один способ разделить массив: $$$[~], [4, 1, 2], [~]$$$.