TopCoder

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

50.0% (15/30)

Tags

Description

Bang! 是以義大利-美國西部風格的紙牌遊戲,由Emiliano Sciarra設計並在2002年由daVinci Editrice出版。Bang! 在2004年贏得Origins Award的Best Traditional Card Game of 2003和Best Graphic Design of a Card Game or Expansion,目前已推出五個擴充包,亦設有APPS版本和豪華包等,為桌遊界長壽作品,亦曾被封為台灣四大暢銷桌遊之一。
----資料來源Bang!



今天你與你的好朋友共N位(編號1~N)正在玩Bang!,然而剛玩沒多久,大家都覺得遊戲規則太複雜,都一心只想要用Bang!這張牌去攻擊其他人。因此你們決定把規則改一下,每個人手上會有$a_i$張Bang!,編號1~N依序出牌只出一輪,因為你的其中一位朋友有強迫症,他規定每一次出牌都必須出完手上所有的Bang!,每位玩家可以選擇要不要出牌,但每一次出牌的張數都必須$\ge$上一位出牌的張數。大家聽完遊戲規則之後,其中一位校排兩位數的朋友便覺得算出最多有幾張Bang!可以被出出來是一個很有趣的問題,而校排942的你為了挽回顏面,決定寫出一個程式來計算。

Input Format

第一行輸入一個$N$ $(1 \le N \le 10 ^ 5 )$ (若N = 1代表你沒朋友一切都是你想像的)
接著輸入$N$個數字$a_i$ $(1 \le a_i \le 10 ^ 5)$代表編號1~N的玩家分別有幾張Bang!

Output Format

請輸出最多可以有幾張Bang!被出出來?

Sample Input

Sample Input #1
2
2 1

Sample Input #2
10
1 2 3 4 5 7 6 7 9 10

Sample Input #3
5
1 100 10 20 30

Sample Output

Sample Output #1
2

Sample Output #2
48

Sample Output #3
101

Hints

子任務(測資)額外限制分數
1(0~4)$N \le 1000$40
2(5~9)60

Sample #1 編號1的玩家出牌
Sample #2 編號1,2,3,4,5,6,8,9,10出牌
Sample #3 編號1,2 的玩家出牌

Problem Source

Problem set by Polarz

Subtasks

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