Get Maximum Sum of Strengths

Given an integer array arr of length n, you may perform the following operation any number of times (possibly 0): choose an index i (0≤i<n−1) and swap arr[i] and arr[i+1]. Over the whole process, each element of the array may take part in at most one swap.

The strength of index i (0-based) is defined as arr[i]×(i+1). Find the maximum possible value of Σ arr[i]×(i+1) (i from 0 to n−1) after all operations.

输入格式

The first line contains an integer n; the second line contains n integers arr[0..n−1], separated by whitespace. 1≤n≤100000, 1≤arr[i]≤100000.

输出格式

Output one integer: the maximum strength sum.

样例 1

输入：

5
1 9 7 3 2

输出：

66

样例 2

输入：

4
2 1 4 3

输出：

30

样例 3

输入：

3
1 2 5

输出：

20

样例说明

Example 1: swapping arr[2] and arr[3] gives [1,9,3,7,2], with strength sum 1×1+2×9+3×3+4×7+5×2=66. Example 2: swapping (arr[0],arr[1]) and (arr[2],arr[3]) gives [1,2,3,4], with strength sum 30. Example 3: no swap is needed; the strength sum is 1×1+2×2+3×5=20.