TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

84.6% (66/78)

Submission's AC Ratio

38.8% (113/291)

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

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10