MLK - Milk Trading

Hareedi and Hanadt live in a village with N houses built next to each other along one straight roadway with equal distances between adjacent houses. Some people own cows and sell the milk their cows produce, while others do not own cows and may need to buy milk.

Every morning, Hareedi and Hanadi transport milk around the village such that everyone buys or sells the exact number of bottles they want. Transporting one bottle of milk from one house to an adjacent house results in one unit of work. Fortunately, the number of milk bottles needed by people is always equal to the number of milk bottles sold by cow owners.

Task

write a program that is given the number of milk bottles that people at each house needs to buy or sell, represented as an integer, finds the minimum work necessary to transport the bottles from sellers to buyers.

Constraints

2 ≤ N ≤ 1,000,000 - the number of houses.

-1000 ≤ Bi ≤ 1000 - an integer representing the number of bottles to be bought from or sold at the house at position i.

There are 28 test cases.

Input

  • Line 1 contains the integer N, the number of houses.
  • Each of the next N lines contains an integer Bi. If Bi > 0 then people in house i are cow owners and want to sell Bi bottles of milk. If Bi ≤ 0 then people at house i are not cow owners and want to buy Bi bottles of milk.

Output

  • A single line containing a single integer, the minimum work units necessary to transport the bottle of milk.

Example

Input:
5
5
-4
1
-3
1

Output:
9

Explanation

There are 5 houses as shown in the table.

Position 1 2 3 4 5
Bottles 5 -4 1 -3 1


4 bottles are transported from house 1 to house 2, 1 bottle from house 1 to house 4, 1 bottle from house 3 to house 4, 1 bottle from house 5 to house 4.


Added by:Rofael Emil
Date:2010-10-19
Time limit:0.203s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Egyptian Olympiad in Informatics ( EOI ) 2009, August 14 - 21, Cairo

hide comments
2011-04-03 12:46:45 :D
Although time limit seems very thight for that kind of data size, I managed to get AC with scanf. Note that it wasn't the 0.29 time from solutions board, but 2.81 :)
2010-11-24 17:18:31 Ravi Kiran
The problem is similar to GERGOVIA with raised constraints and a tighter time limit.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.