Given a list of 
~N~ integers, we can take two adjacent integers, remove both of them, and insert the larger of the
two where the two integers originally were. This incurs cost equal to the larger of the two integers. Compute the
minimum cost needed to reduce this list to having just one integer.
Constraints
~1 \le N \le 10^6~
~0 \le a_i \le 10^9~
For at most 30% of marks, 
~N \le 500~.
For at most 50% of marks, 
~N \le 20\,000~.
Input Specification
The first line will contain a single integer, ~N~.
Each of the next ~N~ lines will contain an integer 
~a_i~, the integers of the list
in order.
Output Specification
Output the minimum cost.
Sample Input
3
1
2
3
Sample Output
5
Comments
Wouldn't the second constraint be better written as
