TopCoder

dnda
Burn chicken everyday...

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

16.7% (1/6)

Tags

Description

巷口的便利商店又推出了神奇的活動了!這次活動的內容是這樣子的,只要繳交入場費,參加者就可以在 10 秒內任意的將便利商店的商品裝到店家提供的籃子裡面,時間結束後,參加者就可以免費的帶走籃子裡面的所有東西。然而,因為這實在是太好康了,因此店家還加上了一項規則:如果參加者拿到了價錢為連續的商品,那麼就違反了規定,而參加者必須要用原本的價錢購買籃子內的所有商品 (當然,可以用入場費全額折抵)。

舉例來說,你可以拿 60 元的蘋果汁、60 元的義大利麵、500 元的威士忌跟 1000 元的儲值卡;但你不能拿 1 罐 29 元的糖果跟 1 盒 30 元的微波食品。

當然,你已經決定要參加這項活動了,但在開始之前你決定寫支程式來算算看怎麼拿才能最大化拿到的商品總價值。

Input Format

輸入包含兩行。

第一行為一個正整數 $N$,代表商品的數量。

第二行包含 $N$ 個正整數 $a_i$,代表 $N$ 項商品各自的價錢。

  • $1\le N\le 10^ 5$
  • $1\le a_i\le 10^ 9$

Output Format

輸出一個正整數,代表最大可獲得的商品總價值。

Sample Input 1

5
1 2 3 4 5

Sample Output 1

9

Sample Input 2

6
5 2 3 4 5 6

Sample Output 2

13

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~17 N <= 3000 10
3 18~33 商品價值不重複 10
4 0~43 無額外限制 80

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2 4
1 1000 262144 65536 1 2 4
2 1000 262144 65536 2 4
3 1000 262144 65536 2 4
4 1000 262144 65536 2 4
5 1000 262144 65536 2 4
6 1000 262144 65536 2 4
7 1000 262144 65536 2 4
8 1000 262144 65536 2 4
9 1000 262144 65536 2 4
10 1000 262144 65536 2 4
11 1000 262144 65536 2 4
12 1000 262144 65536 2 4
13 1000 262144 65536 2 4
14 1000 262144 65536 2 4
15 1000 262144 65536 2 4
16 1000 262144 65536 2 4
17 1000 262144 65536 2 4
18 1000 262144 65536 3 4
19 1000 262144 65536 3 4
20 1000 262144 65536 3 4
21 1000 262144 65536 3 4
22 1000 262144 65536 3 4
23 1000 262144 65536 3 4
24 1000 262144 65536 3 4
25 1000 262144 65536 3 4
26 1000 262144 65536 3 4
27 1000 262144 65536 3 4
28 1000 262144 65536 3 4
29 1000 262144 65536 3 4
30 1000 262144 65536 3 4
31 1000 262144 65536 3 4
32 1000 262144 65536 3 4
33 1000 262144 65536 3 4
34 1000 262144 65536 4
35 1000 262144 65536 4
36 1000 262144 65536 4
37 1000 262144 65536 4
38 1000 262144 65536 4
39 1000 262144 65536 4
40 1000 262144 65536 4
41 1000 262144 65536 4
42 1000 262144 65536 4
43 1000 262144 65536 4