You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

小学生取舍非常想玩王者荣耀，但是他的妈妈告诉他，他需要在小猿口算上进行pk，赢一次就能够玩一个小时的王者荣耀，但是最近大学生不讲武德，天天在pk里炸鱼，导致他一把也没有赢，因此一把王者也没有玩到，他非常愤怒。

为了报复大学生，他请自己的研究生哥哥ikun出了一道题并放入小猿口算的题库中，为了保证取舍能够稳赢大学生，ikun结合了小学生最喜欢的跳格子。

给你一个长度为 $n$ 的正整数数组 ${a_i}$ $(0 \leq i \leq n-1)$ 。

你的目标是从 $a_0$ 出发，到达 $a_{n - 1}$ 处。若你当前处于$a_i$处，你可以移动到任意$a_j (i < j \leq n-1)$处。

从 $a_i$ 跳到 $a_j$ 的得分为 $(j - i) * a_i$ 。你需要求出到达 $a_{n-1}$ 处获得的最大总得分。

凭借这一道题，取舍在小猿口算中大杀四方，作为大学生的你决定出手，制裁小学生。

Input Format

第一行输入一个正整数$n$($1 \leq n \leq 10^5$)，表示数组的长度。

第二行输入 $n$ 个整数$a_0$,$a_1$...$a_{n-1}$（$1\leq a_i \leq 10^5$）,表示数组中的元素。

Output Format

输出到达$a_{n-1}$处获得的最大总得分。

Sample

输入 #1

4
1 3 1 5

输出 #1

7

输入 #2

5
4 3 1 3 2

输出 #2

16

样例1:一开始跳到 $a_1$ 处，然后跳到 $a_3$ 处。总得分为 1 * 1 + 2 * 3 = 7 。

样例2:直接跳到 $a_4$ 处。总得分为 4 * 4 = 16 。