在電影節中,有 $N$ 部電影依序被放映,第 $i$ 部電影會帶給你滿足度 $a_i$。每看完一部電影,你可以選擇在緊接下來的時間看這部電影的影評,同樣會給你帶來 $a_i$ 的滿足度,但是你將會錯過下部電影的播放時間。
如果你選擇看影評,你只能在緊連的下一部電影時間看影評,而且你只會錯過下一部電影。如果你看的影評是來自最後放映的電影,則你不會錯過任何電影。請問所能達成最大滿足度為何。
輸入第一行是一個整數 $N$ 代表人數。
第二行是 $N$ 個以空白分隔的整數 $a_i$,代表電影依序的滿足度。
輸入保證 $1\le N\le 10^ 5$,$1\le a_i\le 1000$。
輸出一行一個整數代表最大可能的滿足度。
ZeroJudge
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~12 | 無額外限制 | 100 |