人员重排

时间限制：1 秒
内存限制：256 MB
输入：标准输入
输出：标准输出

题目描述

曼哈顿项目已进入最终阶段，罗伯特·奥本海默计划将所有员工集中到同一个团队，以便进行最终的计算检查和收尾工作。目前员工在一栋大楼里工作，大楼中有 $n$ 个大型研究设备厅。第 $i$ 个厅里恰好有 $a_i$ 名员工。大厅沿直线排列，因此一名员工每次只能移动到相邻编号的大厅。

奥本海默意识到，每位员工都需要自己的设备才能工作，因此不能简单地将所有人集中到一个大厅：移动员工需要搬运其所有设备，这既昂贵又耗时，而这些时间本可用于研究。因此，管理层希望以最少的代价完成团队合并。复杂度定义为所有员工从他们当前所在大厅出发，最终移动到目标大厅所需经过的相邻大厅转移次数之和。

请帮助找到合并过程的最小可能复杂度。最高指挥部预先对您的合作表示感谢。

输入格式

第一行包含一个整数 $n$ ——曼哈顿项目大楼中的大厅数量（$1 \le n \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_i$ ——第 $i$ 个大厅的员工人数（$1 \le a_i \le 10^9$）。

输出格式

输出一个整数 —— 将所有员工集中到同一个大厅所需的最小复杂度。

样例

样例 1

输入

4
1 3 2 5

输出

10

样例 2

输入

5
1 2 3 4 5

输出

15