题目描述

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

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

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

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

输入格式

第一行：单个整数 $n$； 第二行：$n$ 个整数 $a_1,a_2,⋯,a_n$。

输出格式

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

样例数据

4
-10 10 20 -20

30

5
100 -10 -20 -30 -40

300

说明：$10+2*20+3*30+4*40=10+40+90+160=300$

提示

对于$30\%$数据，$1 \leq n \leq 10$，

对于$60\%$数据，$1 \leq n \leq 100$，

对于$100\%$数据，$1 \leq n \leq 10^5 ,-10^5 \leq a_i \leq 10^5$