题目描述

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

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

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

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

输入格式

第一行：单个整数表示 $n$。

第二行：$n$ 个整数表示 $a_1, a_2, \dots, 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

数据范围

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