题目描述

轩轩和凯凯正在玩一款叫《龙虎斗》的游戏，游戏的棋盘是一条线段，线段上有 $n$ 个兵营（自左至右编号 $1\sim n$），相邻编号的兵营之间相隔 $1$ 厘米，即棋盘为长度为 $n-1$ 厘米的线段。$i$ 号兵营里有 $c_i$ 位工兵。

下图为 $n=6$ 的示例：

轩轩在左侧，代表“龙”；凯凯在右侧，代表“虎”。他们以 $m$ 号兵营作为分界，靠左的工兵属于龙势力，靠右的工兵属于虎势力，而第 $m$ 号兵营中的工兵很纠结，他们不属于任何一方。

一个兵营的气势为：该兵营中的工兵数 $\times$ 该兵营到 $m$ 号兵营的距离；参与游戏一方的势力定义为：属于这一方所有兵营的气势之和。下图为 $n=6,m=4$ 的示例，其中红色为龙方，黄色为虎方。

现在告诉你每一个兵营的工兵数量，请你设定分界兵营，使龙虎的总战斗力差值最小。请求出这个差值。

输入格式

第一行，包含一个整数 $n$。

第二行，包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$。

输出格式

一行，一个整数，表示答案。

输入样例 #1

5
1 2 3 4 5

输出样例 #1

5

输入样例 #2

1
7

输出样例 #2

0

输入样例 #3

6
1 1 1 1 1 1

输出样例 #3

3

数据范围与约定

对于 $50\%$ 的数据：$1\le n\le 10^2$，$0\le c_i\le 10^2$。

对于 $100\%$ 的数据：$1\le n\le 10^5$，$0\le c_i\le 10^9$。