题目描述

有$N$张扑克牌，第$i$张的数字是$a_i$，初始时候在坐标$i$，保证他们是一个$1...N$的排列。

现在，你每次可以把一摞牌A挪到另一摞牌B上，前提条件是：

A所在的这一摞牌的最大值，刚好是B所在的这一摞牌的最小值$-1$。

代价是这两摞牌当前的坐标差的绝对值乘以A,B的牌数之和。

执行完这次操作以后，A这一摞牌所在坐标是空的，B这一摞牌所在坐标变成了原先的A+B这么多牌。

问：最小需要多少代价，能把所有的牌合成一摞。

输入格式

第一行$N(1\leq N\leq 500)$。

第二行$N$个数字表示$a_i$。

输出格式

一个数字表示答案。

样例输入1

3
1 3 2

样例输出1

5

样例解释

先把牌$2$移动到牌$3$，代价是$2$，再把牌$1$移动到牌$2,3$所在位置，代价是$3$。