Description

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

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

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

Format

Input

第一行一行一个整数n，第二行n个整数代表该序列。

Output

一行一个整数表示删完序列的最小代价。

Samples

2
3 2

5

Hint

1<=n<=106，|ai|<=107