Задан массив \(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\) является максимально возможной.
Выходные данные
Выведите одно целое число — максимально возможное значение \(sum_1\), удовлетворяющее условию \(sum_1 = sum_3\).
Очевидно, всегда существует хотя бы один способ разбить массив нужным образом (если \(a=c=0\) и \(b=n\)).
Примечание
В первом тестовом примере только одно возможное разбиение, которое максимизирует \(sum_1\): \([1, 3, 1], [~], [1, 4]\).
Во втором тестовом примере существует единственный способ набрать \(sum_1=4\): \([1, 3], [2, 1], [4]\).
В третьем тестовом примере есть только один способ разделить массив: \([~], [4, 1, 2], [~]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 3 1 1 4
|
5
|
|
2
|
5
1 3 2 1 4
|
4
|
|
3
|
3
4 1 2
|
0
|