在電影節中,有 N 部電影依序被放映,第 i 部電影會帶給你滿足度 ai。每看完一部電影,你可以選擇在緊接下來的時間看這部電影的影評,同樣會給你帶來 ai 的滿足度,但是你將會錯過下部電影的播放時間。
如果你選擇看影評,你只能在緊連的下一部電影時間看影評,而且你只會錯過下一部電影。如果你看的影評是來自最後放映的電影,則你不會錯過任何電影。請問所能達成最大滿足度為何。
輸入第一行是一個整數 N 代表人數。
第二行是 N 個以空白分隔的整數 ai,代表電影依序的滿足度。
輸入保證 1≤N≤105,1≤ai≤1000。
輸出一行一個整數代表最大可能的滿足度。
ZeroJudge