题目描述

各城市之间，需要进行物资的调配。给定一个整数 $n$，表示城市数量。再给定一列整数 $a_1, a_2, \cdots, a_n$，表示每个城市生产或者消费物资的数量——

• 正数表示对应城市是生产物资的，其绝对值代表产量；
• 负数表示对应城市是消费物资的，其绝对值代表消费量；

这些城市之间的道路网络呈一条直线，只有编号相邻的城市有道路相连。从某个城市搬运一个单位的物资到相邻城市将产生一个单位的工作量。请设计一个方案，使得每个城市需要的物资都能达成，且运输的总工作量达到最小。

输入数据保证生产总量和消费总量是相等的，即 $a_1+a_2+\cdots+a_n=0$。

输入格式

• 第一行：单个整数表示 $n$。
• 第二行：$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。

输出格式

• 单个整数：表示最优运输方案产生的最少工作总量。

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 10$；
• 对于 $60\%$ 的数据，$1\leq n\leq 100$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100000$，$-100000\leq a_i\leq 100000$；

样例数据

输入:

4
-10 10 20 -20

输出:

30

输入:

5
100 -10 -20 -30 -40

输出:

300

说明:

10+2*20+3*30+4*40=10+40+90+160