T2 糖果分享

时间：$1s$

空间：$256M$

题目描述

小$W$ 和 小$Z$ 正在分享一些糖果，这些糖果总共有 $n$ 个，按照顺序排成一排，第 $i$ 个糖果有一个美味程度 $a_i$，小$W$ 和 小$Z$ 站在一排糖果的两侧准备接受分配。

现在你要为他们分配糖果，你每次可以指定一个人拿糖果，被指定的人会从未被取走的糖果的最左端拿一个糖果。（注意：小$W$ 和 小$Z$ 方向相对，虽然都是从最左端取，但是 小$W$ 取走的是剩余的糖果中编号最小的，小$Z$ 取走的是剩余的糖果中编号最大的）

由于糖果必须全部被分配，所以你必须指定 $n$ 次拿糖果的人。

请问以这种分配方式，小$W$ 得到的所有糖果美味程度的和 小$Z$ 得到的所有糖果的美味程度的和相差最少是多少。

输入格式

第一行一个正整数 $n$，接下来一行 $n$ 个由空格隔开的整数 $a_i$，具体含义如题目描述。

输出格式

一行一个非负整数表示答案。

样例

input1

3
1 2 3

output1

0

input2

3
1 3 3

output2

1

数据范围

对于全部数据 $1\le n\le2\times10^5$，$1\le a_i\le10^9$。