在魔幻世界中，造物主管辖着n个地盘，n个地盘彼此相邻且相邻的两个地盘之间距离为1，有些地方有人死亡，有些地方有人出生，死亡数与出生数相等，造物主想要所有死亡的人均转世到出生的人身上，但是，这需要他付出一定的代价，每让一个人转世，他需要付出的代价是两个地盘之间的距离，比如当第三个地盘的人转世到第五个地盘的人身上，需要花费2点代价，造物主希望花费的代价最少，请你算出造物主最佳决策下的最少代价花费
输入描述:
测试有多组测试数据
对于每组测试数据，第一行输入一个n（若n为0，则程序终止）
第二行输入n个数a1,a2...an，ai分别表示第i个地盘的净出生人数或净死亡人数，由空格隔开
正数表示该地净出生人数，负数表示净死亡人数
输出描述:
对于每组测试样例，输出一行一个数，表示最少代价花费
示例1
输入
复制
6
-1000 -1000 -1000 1000 1000 1000
5
5 -4 1 -3 1
0
说明
对于第一组样例，从第一个地盘转世到第四个地盘1000人，从第二个地盘转世到第五个地盘1000人，从第三个地盘转世到第六个地盘1000人，每一次移动都花费代价3000，一共花费3000*3=9000
备注:
(1 ≤ n ≤ 100000)
保证最少代价花费在64位带符号整数的范围内
1.所有死亡的人均要找地方进行转世
2.每个人是一个独立的个体，在同一个地方死亡的人有可能转世去同一个地方，也可能转世去不同的地方
3.输入的数据表示的是每个地方的净出生或者净死亡人数；
例如1号地盘死亡5个人，出生2个人，那么净死亡人数就是3个人；
当净死亡人数为3个人的时候，只是表示死亡的人数比出生人数多3个人，而并非死亡人数就是3个人；
在这种情况下，真正死亡的人数有多个解，只是满足等式：死亡人数-出生人数=3