{"raw_statement":[{"iden":"statement","content":"You are given an array $d_1, d_2, \\dots, d_n$ consisting of $n$ integer numbers.\n\nYour task is to split this array into three parts (some of which may be empty) in such a way that each element of the array belongs to exactly one of the three parts, and each of the parts forms a consecutive contiguous subsegment (possibly, empty) of the original array.\n\nLet the sum of elements of the first part be $sum_1$, the sum of elements of the second part be $sum_2$ and the sum of elements of the third part be $sum_3$. Among all possible ways to split the array you have to choose a way such that $sum_1 = sum_3$ and $sum_1$ is maximum possible.\n\nMore formally, if the first part of the array contains $a$ elements, the second part of the array contains $b$ elements and the third part contains $c$ elements, then:\n\nsum_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.\n\nThe sum of an empty array is $0$.\n\nYour task is to find a way to split the array such that $sum_1 = sum_3$ and $sum_1$ is maximum possible."},{"iden":"input","content":"The first line of the input contains one integer $n$ ($1 \\le n \\le 2 \\cdot 10^5$) — the number of elements in the array $d$.\n\nThe second line of the input contains $n$ integers $d_1, d_2, \\dots, d_n$ ($1 \\le d_i \\le 10^9$) — the elements of the array $d$."},{"iden":"output","content":"Print a single integer — the maximum possible value of $sum_1$, considering that the condition $sum_1 = sum_3$ must be met.\n\nObviously, at least one valid way to split the array exists (use $a=c=0$ and $b=n$)."},{"iden":"examples","content":"Input\n\n5\n1 3 1 1 4\n\nOutput\n\n5\n\nInput\n\n5\n1 3 2 1 4\n\nOutput\n\n4\n\nInput\n\n3\n4 1 2\n\nOutput\n\n0"},{"iden":"note","content":"In the first example there is only one possible splitting which maximizes $sum_1$: $[1, 3, 1], [~], [1, 4]$.\n\nIn the second example the only way to have $sum_1=4$ is: $[1, 3], [2, 1], [4]$.\n\nIn the third example there is only one way to split the array: $[~], [4, 1, 2], [~]$."}],"translated_statement":[{"iden":"statement","content":"你被给定一个包含 $n$ 个整数的数组 $d_1, d_2, dots.h, d_n$。\n\n你的任务是将这个数组分成三个部分（其中一些部分可以为空），使得数组的每个元素恰好属于其中一个部分，且每个部分都是原数组的一个连续子段（可能为空）。\n\n设第一部分的元素和为 $s u m_1$，第二部分的元素和为 $s u m_2$，第三部分的元素和为 $s u m_3$。在所有可能的分割方式中，你需要选择一种使得 $s u m_1 = s u m_3$ 且 $s u m_1$ 尽可能大。\n\n更形式化地，如果第一部分包含 $a$ 个元素，第二部分包含 $b$ 个元素，第三部分包含 $c$ 个元素，则：\n\n$$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.$$\n\n空数组的和为 $0$。\n\n你的任务是找到一种分割方式，使得 $s u m_1 = s u m_3$ 且 $s u m_1$ 尽可能大。\n\n输入的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 2 dot.op 10^5$) —— 数组 $d$ 中的元素个数。\n\n第二行包含 $n$ 个整数 $d_1, d_2, dots.h, d_n$ ($1 lt.eq d_i lt.eq 10^9$) —— 数组 $d$ 的元素。\n\n请输出一个整数 —— 在满足 $s u m_1 = s u m_3$ 的前提下，$s u m_1$ 的最大可能值。\n\n显然，至少存在一种有效的分割方式（例如使用 $a = c = 0$ 且 $b = n$）。\n\n在第一个例子中，只有一种分割方式能最大化 $s u m_1$：$[ 1, 3, 1 ], [ med ], [ 1, 4 ]$。\n\n在第二个例子中，使 $s u m_1 = 4$ 的唯一方式是：$[ 1, 3 ], [ 2, 1 ], [ 4 ]$。\n\n在第三个例子中，只有一种分割数组的方式：$[ med ], [ 4, 1, 2 ], [ med ]$。\n"},{"iden":"input","content":"输入的第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 2 dot.op 10^5$) —— 数组 $d$ 中的元素个数。第二行包含 $n$ 个整数 $d_1, d_2, dots.h, d_n$ ($1 lt.eq d_i lt.eq 10^9$) —— 数组 $d$ 的元素。"},{"iden":"output","content":"请输出一个整数 —— 在满足 $s u m_1 = s u m_3$ 的前提下，$s u m_1$ 的最大可能值。显然，至少存在一种有效的分割方式（例如使用 $a = c = 0$ 且 $b = n$）。"},{"iden":"examples","content":"输入\n5\n1 3 1 1 4\n输出\n5\n\n输入\n5\n1 3 2 1 4\n输出\n4\n\n输入\n3\n4 1 2\n输出\n0"},{"iden":"note","content":"在第一个例子中，只有一种分割方式能最大化 $s u m_1$：$[ 1, 3, 1 ], [ med ], [ 1, 4 ]$。在第二个例子中，使 $s u m_1 = 4$ 的唯一方式是：$[ 1, 3 ], [ 2, 1 ], [ 4 ]$。在第三个例子中，只有一种分割数组的方式：$[ med ], [ 4, 1, 2 ], [ med ]$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array.  \nLet $ D = (d_1, d_2, \\dots, d_n) $ be a sequence of positive integers.  \n\nA **split** of $ D $ is defined by two indices $ a, b \\in \\{0, 1, \\dots, n\\} $ with $ 0 \\le a \\le b \\le n $, partitioning the array into three contiguous parts:  \n- First part: $ D[1:a] = (d_1, \\dots, d_a) $, sum $ s_1 = \\sum_{i=1}^a d_i $  \n- Second part: $ D[a+1:b] = (d_{a+1}, \\dots, d_b) $, sum $ s_2 = \\sum_{i=a+1}^b d_i $  \n- Third part: $ D[b+1:n] = (d_{b+1}, \\dots, d_n) $, sum $ s_3 = \\sum_{i=b+1}^n d_i $  \n\nBy convention, the sum over an empty range is 0.\n\n**Constraints**  \n1. $ 1 \\le n \\le 2 \\cdot 10^5 $  \n2. $ 1 \\le d_i \\le 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 0 \\le a \\le b \\le n $  \n\n**Objective**  \nMaximize $ s_1 $ subject to the constraint $ s_1 = s_3 $:  \n$$\n\\max_{\\substack{0 \\le a \\le b \\le n \\\\ s_1 = s_3}} s_1\n$$","simple_statement":null,"has_page_source":false}