描述

正如你可能从漫画《高卢英雄历险记之酋长的盾牌》中了解到的，热尔戈维亚（Gergovia）由一条街道组成，并且这个城市的每个居民都是葡萄酒推销员。你可能想知道这种经济模式是如何运作的？非常简单：每个人都从城市里的其他居民那里购买葡萄酒。每天，每个居民都会决定他想要购买或出售多少葡萄酒。有趣的是，需求和供给总是相等的，这样每个居民都能得到他想要的。

然而，有一个问题：把葡萄酒从一所房子运到另一所房子需要花费力气。由于所有的葡萄酒质量都一样，热尔戈维亚的居民并不在乎他们和哪些人进行交易，他们只对买卖特定数量的葡萄酒感兴趣。他们足够聪明，能够想出一种交易方式，使得运输所需的总力气最小化。

在这个问题中，要求你重现热尔戈维亚一天的交易情况。为了简单起见，我们假设房子沿着一条直线建造，相邻房子之间的距离相等。把一瓶葡萄酒从一所房子运到相邻的房子需要花费一个单位的力气。

输入

输入由几个测试用例组成。 每个测试用例以居民的数量 $n$ （$2 \leq n \leq 100000$）开始。接下来的一行包含 $n$ 个整数 $a_{i}$（$-1000 \leq a_{i} \leq 1000$）。如果 $a_{i} \geq 0$，这意味着住在第 $i$ 所房子的居民想要购买 $a_{i}$ 瓶葡萄酒，否则，如果 $a_{i} < 0$，他想要出售 $-a_{i}$ 瓶葡萄酒。你可以假设数字 $a_{i}$ 的总和为 0。 最后一个测试用例后面跟着一行包含 0 的内容。

5
5 -4 1 -3 1
6
-1000 -1000 -1000 1000 1000 1000
0

输出

对于每个测试用例，打印出满足每个居民需求所需的最小力气单位数量。你可以假设这个数字适合存储在一个有符号的 64 位整数中（在 C/C++ 中你可以使用数据类型 “long long” 或 “__int64”，在 JAVA 中使用数据类型 “long”）。

9
9000

来源

2006 年乌尔姆大学本地竞赛