Background

当她朝我微笑的时候，我心想，这下子完了，为了能再看到这个笑容，我肯定会做出很多明知道不该做的事情吧。

Description

你有一个长度为 n 序列 {a}(序列下标从1开始) ，每次可以从任意位置 i 花费 $a_i \times i$ 的代价来把 $a_i$ 删除。

注意 ，删除后 $a_i$ 后面的数会依次向前补上（下标 -1 ) 。

求把整个序列删完的最小代价。

Format

Input

第一行输入一个n表示这个集合的元素个数$(0<n<10000)$ 第二行输入n个元素$a_i(-1000000<a_i<1000000)$

Output

输出删除完后的最小代价

Samples

3
1 2 3

6

Limitation

1s, 1024KiB for each test case.