时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有 \(n\) 个村庄等距地分布在一条笔直的公路上，编号为 \(1..n\)。每个村庄要么买水果，要么卖水果。设第 \(i\) 个村庄对水果的需求为 \(a_i\) ，其中 \(a_i>0\) 表示买水果，\(a_i<0\) 表示卖水果。所有村庄供需平衡，即所有 \(a_i\) 之和等于 0。把 \(k\) 个单位的水果从一个村庄运到相邻村庄需要 \(k\) 个单位的劳动力。计算最少需要多少劳动力可以满足所有村庄的需求。输出保证在 64 位带符号整数的范围内。

【输入格式】

　　若干组数据，每组数据为两行。
　　对于每组数据，第一行有一个整数 \(n\)，第二行有 \(n\) 个整数：\(a_1,a_2,…,a_n\)，其中 \(a_i\) 表示地 \(i\) 个村庄的水果需求量。输入的最后以 0 结尾。

【输出格式】

　　每组数据一行，每行一个整数，表示最少需要的劳动力数量。

【输入输出样例】

　Input

10
3 -1 -2 9 -4 -1 -7 9 -7 1
5
1000 -1000 1000 0 -1000
0

　Output

33
3000

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤100000\)，\(-1000 ≤ a_i ≤ 1000\)。

【来源】

　　Mr.he