给定一个数组 $$$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$$$)。
示例
输入 #1
5 1 3 1 1 4
输出 #1
5
输入 #2
5 1 3 2 1 4
输出 #2
4
输入 #3
3 4 1 2
输出 #3
0
注意
在第一个示例中,只有一种可能的分割可以最大化 $$$sum_1$$$:$$$[1, 3, 1], [~], [1, 4]$$$。
在第二个示例中,获得 $$$sum_1=4$$$ 的唯一方法是:$$$[1, 3], [2, 1], [4]$$$。
在第三个示例中,只有一种方法可以分割数组:$$$[~], [4, 1, 2], [~]$$$。