题目描述

现有 $n$ 个人想排队接水，每个人都有一个满意度 $a_i$。

假设只有一个水龙头，每个人的接水时间都为 $1$ 分钟，如果一个人最终接到了水，那么他会给 “水龙头管理员” 打分，分数为：他的满意度乘以他接水的结束时间。例如如果一个人的满意度是 $5$，他接水的结束时间是 $3$，那么他打的分数就是 $5 \times 3 = 15$。

没错，你就是那个 “水龙头管理员”。

现在你知道每个人的满意度，你可以按照任意顺序让他们排队接水，请问你能得到的最大的分数之和是多少？

当然，既然你作为 “水龙头管理员”，为了得到最大的分数，你有权利让人不接水。

输入格式

第一行一个整数 $n$，表示有 $n$ 个人。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每个人的满意度。

输出格式

一行一个整数，表示你能得到的最大的分数之和。

样例数据

输入样例 #1

5
0 5 -8 -9 -1

输出样例 #1

14

选择让第 $5、1、2$ 个人排队接水，三人满意度分别为 $-1、0、5$，接水的结束时间分别为 $1、2、3$ 分钟。

那么第一个人的打分为：$-1 \times 1 = -1$

第二个人的打分为：$0 \times 2 = 0$

第三个人的打分为：$5 \times 3 = 15$

所以最大的分数之和为 $-1 + 0 + 15 = 14$，这是最优解。

输入样例 #2

3
4 3 2

输出样例 #2

20

数据范围与提示

对于所有测试数据，保证 $2 \le n \le 2 \times 10 ^ {5}$，$-1000 \le a_i \le 1000$。

备注：本题测试数据为民间数据