{"trustable":false,"sections":[{"title":"","value":{"format":"PLAIN","content":"As you may know from the comic \\Asterix and the Chieftain\u0027s Shield\", Gergovia consists of one street,and every inhabitant of the city is a wine salesman. You wonder how this economy works? Simple enough: everyone buys wine from other inhabitants of the city. Every day each inhabitant decides how much wine he wants to buy or sell. Interestingly, demand and supply is always the same, so that each inhabitant gets what he wants.There is one problem, however: Transporting wine from one house to another results in work. Since all wines are equally good, the inhabitants of Gergovia don\u0027t care which persons they are doing trade with, they are only interested in selling or buying a specific amount of wine. They are clever enough to gure out a way of trading so that the overall amount of work needed for transports is minimized.In this problem you are asked to reconstruct the trading during one day in Gergovia. For simplicity we will assume that the houses are built along a straight line with equal distance between adjacent houses. Transporting one bottle of wine from one house to an adjacent house results in one unit of work.\nInput\nThe input consists of several test cases. Each test case starts with the number of inhabitants n (2\u003c\u003dn\u003c\u003d100000). The following line contains n integers ai(-1000\u003c\u003dai\u003c\u003d1000). If ai \u003e\u003d0, itmeans that the inhabitant living in the i-th house wants to buy ai bottles of wine, otherwise if ai\u003c0,he wants to sell ai bottles of wine. You may assume that the numbers ai sum up to 0.The last test case is followed by a line containing `0\u0027.\n\nOutput\n\nFor each test case print the minimum amount of work units needed so that every inhabitant has his demand fulfilled. You may assume that this number fits into a signed 64-bit integer (in C/C++ you can use the data type \\long long\", in JAVA the data type \\long\").\n\nSample Input\n\n55 -4 1 -3 16-1000 -1000 -1000 1000 1000 10000\n\nSample Output\n\n99000\n\n你可能在漫画《Asterix and the Chieftain\u0027s Shield》中知道,Gergovia只有一条街,每个居民都是卖酒的。你想知道这种经济是如何运作的吗?很简单:每个人都从城市的其他居民那里买酒。每天,每个居民决定他想买多少酒或卖多少酒。有趣的是,需求和供应总是相同的,所以每个居民都能得到他想要的东西。把酒从一户人家运到另一户人家是要花工夫的. 由于所有的酒都是一样好的,所以格果维亚的居民并不关心他们在和哪些人做交易,他们只对出售或购买特定数量的酒感兴趣。他们很聪明地想出了一种交易方式,使运输所需的总体工作量最小化.在这个问题中,你被要求重建一天在Gergovia的交易。为了简单起见,我们将假设房屋是沿着一条直线建造的,相邻房屋之间的距离相等。将一瓶酒从一栋房子运到相邻的房子,就会产生一个单位的工作。\n输入\n输入由若干测试用例组成。 每个测试用例都以居民数n开始(2\u003c\u003dn\u003c\u003d100000)。 下面一行包含n个整数ai(-1000\u003c\u003dai\u003c\u003d1000)。 如果ai\u003e\u003d0,则表示住在第i-th家的居民要买ai瓶酒,否则如果ai\u003c0,他要卖ai瓶酒。最后一个测试用例后面是一行包含 \"0 \"的字样,你可以假设这些数字ai的总和是0。\n\n輸出結果\n\n对于每个测试用例,打印出所需的最小工作单位数量,以使每个居民的需求得到满足。你可以假设这个数字适合于一个有符号的64位整数(在C/C++中,你可以使用数据类型\"\\long long\",在JAVA中,你可以使用数据类型\"\\long\")。\n\n输入示例\n\n5\n5 -4 1 -3 1\n6\n-1000 -1000 -1000 1000 1000 10000\n\n采样输出\n\n9\n9000"}}]}