Dr. SiRaBaSu always has trouble memorizing large numbers. To remember a number x, he will need | x | units of energy.
As a programmer and a notorious problemsetter who enjoy setting very hard problems, he often needs to memorize a
lot of number sequences. Fortunately, he invented a mnemonic to help himself memorize better.
When a sequence of numbers is given, instead of memorizing each number in the sequence, now he memorizes
several consecutive segments and their sum instead. For example, in the sequence <ai> = <1, -3, 2, 4>, he would memorize
the following:
a1 = 1
a2 + a3 = -1
a2 + a3 + a4 = 3
a3 = 2
Then, he is able to reconstruct the original sequence from the information he just memorized.
For example, he can retrieve a4 by using the third equality to minus the second equality.
As mentioned, the total energy needed for him is | 1 | + | -1 | + | 3 | + | 2 | = 7, which is less than
10 units of that in the straightforward way.
(Note that this strategy is not the best in this case. The minimum energy he needed can be 6 here. )
You are going to write a program that helps Dr. SiRaBaSu to determine the best strategy to memorize
the sequence using minimum energy, so he can set more hard problems.
The input may contain no more than 50 cases. In each case, there is an integer n (1<=n<=500) denoting the length of the sequence.
The following n lines describe the sequence, where the i'th line contains an integer representing ai (-10000 <= ai <= 10000).
For each case, please output exactly one integer in a line representing the minimum energy SiRaBaSu
can use to memorize the sequence.