C - Pretty Derby

配点 : $300$ 点
　　

問題文

あなたはトレセン学園に所属する優秀なトレーナーであり、担当のウマ娘の育成に勤しんでいます。
これから $N$ 回のレースが開催され、 $i$ 回目のレースに出場したウマ娘が新しく獲得できるファンの数は $A_i$ 人です。
あなたの仕事は、担当のウマ娘の出場するレースを適切に決めることによって、彼女が獲得するファンの数を最大化することです。
ただし、彼女が疲れてしまうので、 $3$ 回以上連続でレースに出場させることは出来ません。
適切に出場するレースを決めたとき、彼女が獲得できるファンの人数の最大値を求めてください。

制約

• $1\leq N \leq 10^5$
• $1\leq A_i \leq 10^9$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

出力

答えを出力してください。

入力例1

5
5 2 4 9 1

出力例1

18

$1,3,4$ 回目のレースに出場させるのが良いです。獲得できるファンの数は $5+4+9=18$ 人となり、これが最適です。
例えば$1,3,4,5$ 回目のレースに出場させると $19$ 人のファンが獲得できますが、 $3,4,5$ 回目のレースで $3$ 回連続で出場してしまっているため、このような出場するレースの決め方は出来ないことに注意してください。
　

入力例2

1
100000

出力例2

100000

$1$ 回しかレースが開催されないので、そのレースにそのまま出場させれば良いです。 　
　

入力例3

10
100 100 100 100 100 100 100 100 100 100

出力例3

700