题目描述

直线上有 $n$ 个等距的村庄，每个村庄要么买酒，要么卖酒。

设第 i 个村庄对酒的需求为 $a_i$($-1000<=a_i<=1000$)，其中 $a_i>0$ 表示买酒， $a_i<0$ 表示卖酒。

所有村庄供需平衡，即所有 $a_i$之和等于$0$。把 $k$ 个单位的酒从一个村庄运到相邻村庄需要 $k$ 个单位的劳动力。

计算最少需要多少劳动力可以满足所有村庄的需求。输出保证在 64 位带符号整数的范围内。

输入格式

若干组数据，每组数据为两行。

对于每组数据，第一行有一个整数$N$，表示有$N$个酒窖，第二行有N个整数,从$a1,a2......an$。

输入的最后以 0 结尾。

输出格式

每组数据一行，每行一个整数，表示总费用。

样例

输入

10

输出

3 -1 -2 9 -4 -1 -7 9 -7 1
5
1000 -1000 1000 0 -1000
0

33
3000

提示

数据范围：$2 <= n <= 100 000$