严神在一条街上想要开一家商店。他这家商店将成为街上唯一的商店。
这条街可以看成一条直线。 直线上共有 n 个居民点，从左到右编号为 1 - n . 每两个相邻点之间的距离为1. 每个点上可能住着若干人，也有可能没有住人。严神知道，每个人的不悦指数，等同于他走到商店的距离。而多个人的不悦指数等同于所有人每人的不悦指数之和。因为严神想要方便大家， 他希望整条街上的人都来买他的商品， 且不悦指数之和最少。他想知道， 这个最小的不悦指数是多少。
请注意， 严神只能将商店开在这 n 个点的其中一个而不能开在两个点中间。
输入共 2 行。
第 1 行， 一个整数 n , 代表街上的点数。
第 2 行， 共 n 个整数， 代表每个点居住的人数。
输出仅一个整数， 最小的不悦指数。
4 1 2 0 4
7
严神可将商店开在 4 号居民点， 这样不悦指数为 1 * （4 - 1） + 2 * （4 - 2） = 7. 可以证明， 没有不悦指数小于7的方法。
对于 30% 的数据， n \leq 10^3 .
对于 100% 的数据， 1 \leq n \leq 10^5, 0 \leq seg_i \leq 10^9 .