數字合併

黑板上有n個數字寫成一排，現在每次選擇兩個相鄰的數字，把比較小的那個 數字擦掉(如果兩個數字一樣大，那麼擦掉任何一個都可以。)然而，這些步驟需要花費，這個花費恰好等於留下來的那個數字(比較大的那個)。 

請問經過n-1次操作，黑板上會剩下的那個數字是多少？ 

你以為問題這麼簡單嗎？錯! 

真正的問題是： 

請問經過n-1次操作，黑板上會剩下最大的那個數字，所有操作方法中，最小總花費是多少？
輸入說明 ：
輸入檔只包含一筆測試資料。 
第一列有一個正整數n(1<=n<=1,000,000)代表黑板上數字的個數。 
接下來有n列，每列有一個正整數(1<=數字<=109)依序代表黑板上的每個數字。
輸出說明 ：
請輸出經過n-1次操作之後，所需的最小總花費。
範例輸入 ： 
5 
7 
4 
5 
2 
5
範例輸出 ：
22

提示 ：
消掉4、花費5； 
消掉2、花費5； 
消掉5、花費5； 
消掉5、花費7； 
總花費是5+5+5+7=22。