2259: 直线运输

Memory Limit:128 MB Time Limit:1.000 S
Creator:
Submit:27 Solved:7

Description

给定一个正整数 nn,表示一个国家的城市数量。再给定一列整数a1, a2, a3, a4, a5....an表示每个城市生产或者消费物资的数量,正数表示生产数量,负数表示消费数量。输入数据保证生产总量和消费总量是相等的,即a1+a2+a3+a4+a5....+an=0
这些物资可以从一个城市搬运到另一个城市,一次搬运必须在两个编号相邻的城市间进行,若搬运一个单位数量的物资到一个相邻的城市,将产生一个单位的工作量。请设计一个方案,使得所有物资都从生产城市搬运至消费城市,且每个消费城市需要的物资数量都能得到满足,且搬运的总工作量达到最小。

Input

第一行:单个整数表示n;
第二行:n个整数表示a1, a2, a3, a4, a5....an;

Output

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

Sample Input

4
-10 10 20 -20

Sample Output

30

HINT

对于30%的数据,1≤n≤10; 
对于60%的数据,1≤n≤100; 
对于100%的数据 1≤n≤100000,−100000≤ai≤100000;