TopCoder

Thumb output jddoia
$\huge 南ことり$
$https://www.ototot.com.tw/TIOJ/ \\我要拿牌、去東京、變紅色,那就努力吧 \\ 確かな今よりも新しい夢つかまえたい$

User's AC Ratio

76.9% (40/52)

Submission's AC Ratio

31.2% (62/199)

Description

自從帳號被刪掉之後, 修羅少年越加的愛台灣.
而看到處於如此危險局面的台灣, 修羅少年決定幫助台灣建立防線的連絡網.

現在修羅少年已經選定了 n 個排成一條線的軍事基地,
打算在這 n 個軍事基地中任兩個之間都建立連絡網.
然而事情並沒有這麼簡單, 兩個相鄰的軍事基地之間都會有一些障礙,
每團障礙都會有一個 G 值, 代表連絡網的電波強度至少要為 G 才能穿過它.
而且如果要在某兩個軍事基地 a, b 之間建立連絡網,
電波必須強到能穿越 a 到 b 間所有障礙才行.

現在修羅少年已經找出了這 n - 1 團障礙的 G 值分別是多少,
請問建立起來的連絡網, 所有電波強度的總和至少是多少?

Input Format

第一行有一個正整數 n
第二行開始有 n - 1 個整數,
其中第 i 個數字代表軍事基地 i 與 i + 1 之間的障礙的 G 值

(1 <= n <= 1000000, 0 <= 任意G <= 231 - 1)
至少有 40% 的測資 n <= 2000
至少有 80% 的測資 n <= 200000

Output Format

請輸出一個數字代表所有電波強度的總合至少是多少.

(保證答案不會超過263 - 1)

Sample Input

6
4 3 2 4 3

Sample Output

55

Hints

Problem Source

原TIOJ1637 / Problem Setter: worm

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 65536
1 10000 65536 65536
2 10000 65536 65536
3 10000 65536 65536
4 10000 65536 65536
5 10000 65536 65536
6 10000 65536 65536
7 10000 65536 65536
8 10000 65536 65536
9 10000 65536 65536