User's AC Ratio

95.5% (42/44)

Submission's AC Ratio

52.7% (69/131)

Description

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

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

你以為問題這麼簡單嗎?!

真正的問題是:

請問經過n-1次操作,黑板上會剩下最大的那個數字,所有操作方法中,最小總花費是多少?

Input Format

輸入檔只包含一筆測試資料。
第一列有一個正整數n(1<=n<=1,000,000)代表黑板上數字的個數。
接下來有n列,每列有一個正整數(0<=數字<=109)依序代表黑板上的每個數字。

Output Format

請輸出經過n-1次操作之後,所需的最小總花費。

Sample Input

5
7
4
5
2
5

Sample Output

22

Hints

消掉4、花費5;
消掉2、花費5;
消掉5、花費5;
消掉5、花費7;
總花費是5+5+5+7=22。

Problem Source

原TIOJ1225 / TIOJ 2008例行賽03-Elite (prob G)。BALTIC OLYMPIAD IN INFORMATICS 2007 Day2(prob 6,Sequence)。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
For Testdata: 17 ~ 17, Score: 5
For Testdata: 18 ~ 18, Score: 5
For Testdata: 19 ~ 19, Score: 5
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1900 65536 262144
1 1900 65536 262144
2 1900 65536 262144
3 1900 65536 262144
4 1900 65536 262144
5 1900 65536 262144
6 1900 65536 262144
7 1900 65536 262144
8 1900 65536 262144
9 1900 65536 262144
10 1900 65536 262144
11 1900 65536 262144
12 1900 65536 262144
13 1900 65536 262144
14 1900 65536 262144
15 1900 65536 262144
16 1900 65536 262144
17 1900 65536 262144
18 1900 65536 262144
19 1900 65536 262144