Problem Description

ComistryMo和他的小伙伴们最近都很喜欢《葬送的芙莉莲》这一部番，其中有一个角色叫菲伦，灰常滴可爱(●'◡'●)。 但其实她是一个实力雄厚的魔法使，主要攻击手段为普通攻击魔法。在一次控制魔力消耗的训练中，她的师傅芙莉莲给她安排了如下的任务：现在有$n$块石头，下标从$1$开始，每一块石头有一个值为$a_i$，菲伦需要使用普通攻击魔法来击碎所有的石头，她可以从任意位置开始攻击，击碎第$i$块石头需要消耗菲伦$a_i * i$的魔力值。

注意，击碎第$i$块石头之后，后面的石头会向前补齐（下标$-1$）。

虽然菲伦的魔力很多，但是她仍然想知道她最少需要消耗的魔力就可以完成这次训练，因此她拜托旅途中认识的ComistryMo来问问大家这个问题的答案是多少。

Input Format

第一行输入一个正整数 $n$($1 \leq n \leq 1 \times 10^6$)，表示石头的数量。

接下来一行$n$个数，第$i$个数表示$a_i$($1 \leq |a_i| \leq 1 \times 10^7$)，表示第$i$块石头的值。

Output Format

一行一个整数，表示菲伦最小消耗的魔力量。

Sample

样例输入

2
3 2

样例输出

5

Hint

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