INSULENG  Insulation
Give N bricks and a sequence a_{1}...a_{n} as the insulation of them. If we arrange the bricks in that order into a wall then the insulation of the wall is a_{1} + a_{2} + ... + a_{N} + max(0, a_{2}  a_{1}) + max(0, a_{3}  a_{2}) + ... + max(0, a_{N}  a_{N}  1). Your task is to arrange the bricks so that the insulation of the wall is maximum.
Input
 The first line is N (1 <= N <= 10^{5}).
 In each of the next N lines, the i^{th} line is a_{i1}
Output
 The maximum insulation of the wall.
Example
Input:
4
5
4
1
7 Output:
24
hide comments
Mitch Schwartz:
20111104 03:45:54
Input is poorly formatted. 

Egor:
20110318 13:26:03
greed! 

:D:
20110315 11:08:16
I think this problems is set as a challenge (my score for challenges isn't adding up). Please correct that. 

T7:
20110315 07:56:05
The example is 24 if we arrange the bricks like this: 1 5 4 7 ;) 

Eduardo Carrasquero:
20110315 04:53:07
the example is 23 for me...


cegprakash:
20110314 17:53:38
i think such test cases went for me to TLE


:D:
20110314 17:25:44
How did you checked all permutations for N=10^5 :O 

Sushovan Sen:
20110314 17:08:05
I dont understand scoring.. 

Kashyap Krishnakumar:
20110314 15:53:22
@cegprakash: you need not check for all permutations! :P 
Added by:  Hacker7 
Date:  20110314 
Time limit:  0.200s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC ASM64 GAWK MAWK BC CCLANG CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  VNOI 