Wine Trading in Gergovia

As you may know from the comic “Asterix and the Chieftain’s Shield”, Gergovia consists of a single street, and every inhabitant of the city is a wine seller. Wondering how this economy works? It is simple: everyone buys wine from other inhabitants of the city. Every day each inhabitant decides how much wine they want to buy or sell. Interestingly, demand and supply are always equal, so each inhabitant gets exactly what they want.

There is one problem, however: transporting wine from one house to another takes work. Since all wines are equally good, the inhabitants of Gergovia do not care whom they trade with; they only care about buying or selling a specific amount of wine. They are clever enough to arrange the trades so that the total amount of work spent on transport is minimized.

In this problem you are asked to reconstruct one day of trading in Gergovia. For simplicity, assume the houses stand along a straight line with equal spacing between adjacent houses. Transporting one bottle of wine from a house to an adjacent house costs one unit of work.

The input consists of several test cases.

Each test case starts with the number of inhabitants $n$ ($2 \le n \le 100000$). The next line contains $n$ integers $a_i$ ($-1000 \le a_i \le 1000$). If $a_i \ge 0$, the inhabitant living in the $i$-th house wants to buy $a_i$ bottles of wine; if $a_i < 0$, they want to sell $-a_i$ bottles. You may assume that the values $a_i$ sum to $0$.

The last test case is followed by a line containing a single $0$, which ends the input.

For each test case, print on its own line the minimum amount of work needed so that every inhabitant’s demand is fulfilled. You may assume this value fits into a signed 64-bit integer.