题目描述

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

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

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

输入格式

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

输出格式

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

样例输入输出

样例输入

2
3 2

样例输出

5

数据范围

对于 $100%$ 的数据，保证 $1 \le n \le 10^6,∣a_i∣≤10^7$ 。

保证答案在 $-2^{63}$ 到 $2^{63}-1$ 范围内。