1 人解决，2 人已尝试。
1 份提交通过，共有 4 份提交。
9.8 EMB 奖励。
1357. Insulator
单点时限: 2.0 sec
内存限制: 256 MB
The company Insumax produces multilayer thermal insulators. Each of the i layers, i=1, 2, …, n, of such an insulator is characterized by positive insulation coefficient ai. The layers are numbered according to the direction the heat leaks.
heat -> || a1 | a2 | … | ai | ai+1 | … | an || ->
The insulation coefficient of the whole insulator, A, is described by the sum of insulation coefficients of its layers. Moreover, the coefficient A raises if a layer with a smaller insulation coefficient is followed by a layer with a larger coefficient, according to the formula:
For example, the insulation coefficient of the insulator of the form
-> || 5 | 4 | 1 | 7 || ->
is A = (5+4+1+7)+(7-1) = 23.
Task
Write a program which, for given insulation coefficients of layers a1, a2, …, an, determines such an ordering of the layers that the insulation coefficient of the whole insulator is maximised.
输入格式
In the first line there is the number of layers n, 1 <= n <= 100000. In the successive n lines there are coefficients a1, a2, …, an, one per line. Those coefficients are integers satisfying the inequalities 1 <= ai <= 10000.
输出格式
In the first and only line your program should write one integer equal to the largest possible value of the insulation coefficient A of the insulator built of the layers of the given coefficients, put in a particular order.
样例
Input
4 5 4 1 7
Output
24
题目标签