AT_agc050_b [AGC050B] Three Coins

[problemUrl]: https://atcoder.jp/contests/agc050/tasks/agc050_b $ N $ 個のマスが一列に並んでおり、左から右に $ 1 $ から $ N $ までの番号が振られています。 はじめ、すべてのマスは空です。 あなたは、以下の $ 2 $ 種類の操作を任意の順に何度でも行うことができます。 - **連続する** $ 3 $ マスであってコインが置かれていないものを選び、それぞれにコインを置く。 - **連続する** $ 3 $ マスであっていずれにもコインが置かれているものを選び、それぞれからコインを取り除く。 操作を済ませた後、左から $ i $ マス目にコインが置かれているなら、$ a_i $ 点が得られます。 コインがあるマス全てから得られる点数の合計が、あなたの得点です。 得られる最高得点を求めてください。

入力は標準入力から以下の形式で与えられる。 > $ N $ $ a_1 $ $ a_2 $ $ : $ $ a_N $

答えを出力せよ。

### 制約 - $ 3\ \leq\ N\ \leq\ 500 $ - $ -100\ \leq\ a_i\ \leq\ 100 $ - 入力中の全ての値は整数である。 ### Sample Explanation 1 コインが置かれたマスを `o` で、置かれていないマスを `.` で表します。 最適な手順の $ 1 $ つは次の通りです。 `....` $ \rightarrow $ `.ooo` このようにすれば、$ 2\ +\ 3\ +\ 4\ =\ 9 $ 点を得られます。 ### Sample Explanation 2 最適な手順の $ 1 $ つは次の通りです。 `......` $ \rightarrow $ `ooo...` $ \rightarrow $ `oooooo` $ \rightarrow $ `o...oo` このようにすれば、$ 3\ +\ (-1)\ +\ 4\ =\ 6 $ 点を得られます。