TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

94.1% (16/17)

Submission's AC Ratio

61.1% (22/36)

Description

你去過萬里長城嗎?

秦始皇三十三年(前214年),秦始皇派大將蒙恬率領三十萬人北逐匈奴,佔據河套,並修築長城。

「秦已併天下,乃使蒙恬將三十萬眾北逐戎狄,收河南。築長城,因地形,用制險塞,起臨洮,至遼東,延袤萬餘裏,於是渡河,據陽山,逶蛇而北。暴師於外十餘年。」(《史記·蒙恬列傳》)
秦長城把過去秦、趙、魏、燕長城連接起來,從臨洮到遼東的綿延萬里,從此始有「萬里長城」之稱。

秦長城可大致分為西段和北段。西段起於今甘肅省岷縣,循洮河北至臨洮縣,經定西縣向東北至寧夏固原縣、甘肅環縣、陝西靖邊、橫山、榆林、神木,然後向北折至今內蒙古托克托南,抵黃河南岸。
北段即黃河以北的長城沿陰山西段的狼山,向東至大青山北麓,再向東經今內蒙集寧、興和至河北尚義,再向東北經今河北張北、圍場,再向東經撫順、本溪後向東南,終於朝鮮清川江入海處。

在修築北方長城的同時,原諸侯國間用以「互防」的長城被拆毀:
「皇帝奮威,德並諸侯,初一泰平。墮壞城郭,決通川防,夷去險阻。」(《史記·秦始皇本紀》)
秦長城對於抵禦匈奴的騷擾,保障中原生產和生活的安定,起了重要的作用。

秦始皇為了修築長城動用了30萬人,創造了人類建築史上的奇跡。

這一繁重的修築工程,也給當時的人們帶來了極大的痛苦,孟姜女的故事便來源於此。
現在臨洮附近,陰山、大青山一線,都有秦長城遺跡殘存。

回到那個時代,觀察到萬里長城的特色就是城牆一側總是一高一低的。

而你就是建造長城的工程師,你希望你造的城牆越長越好,而建造城牆的建材是石頭,每塊石頭可能有不同的高度。

但是供應石頭的廠商非常討厭,他每送一塊石頭就會問你要不要買,如果你不買,那塊就永遠不會再賣給你。

而秦始皇更討厭,他規定你一買一塊石頭就要馬上用,而且一定要按照購買的順序建造

你透過一些內部的管道,得知廠商即將供應給你的石頭高度的順序,你能建造出多長的城牆呢?

有幾點可能要注意一下:
1.石頭不能疊起來,也不能躺下來,不然間隔的接縫會不整齊,秦始皇會不開心,然後把你『咻碰』!
2.一定要滿足一塊高一塊低的方式,不然秦始皇會不開心,然後把你『咻碰』!
3.城牆的兩側,一定要是比旁邊那塊還高,不然城牆會很醜,使得秦始皇不開心,然後把你『咻碰』!
4.這家廠商相當的優質(因為不優質的話,秦始皇會不開心,然後把他『咻碰』!),每塊石頭的長寬都是一單位,只有高度不均。

Input Format

本題只有一筆測資:

第一行包含一個正整數 n ,代表廠商將供應給你的石頭數量(0 < n <= 1000000)

接下來有一行,有 n 個數字 hi,依照順序代表每塊石頭的高度 (0 < hi < 231)

Output Format

請輸出你最多能建造多長的城牆。

Sample Input

5
5 1 4 2 3

Sample Output

5

Hints

※2008/10/08 輸入格式更改 by peter50216,感謝 SKYLY。
※2008/10/09 題目敘述修正 by hallogameboy,感謝 SKYLY。

Problem Source

原TIOJ1441 / 建中校內培訓第一次模擬考試。
Problem Setter:hallogameboy、peter50216

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, 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
10 10000 65536 65536