006 - 回転SUSHI

時間制限 5 秒 / メモリ制限 512 MB / 得点 13 / x 0 /


TLE
5sec
MLE
512MB
得点
13

もんだい

あなたは、回転寿司にきている。
お寿司はN皿が順番に流れてくる。N皿のお寿司のそれぞれの美味しさがViで表される。
流れてくるお寿司が自分の前に来た時に取ることができるが、このお店のルールで、 連続で皿を取ることが出来ない。
もちろん、自分の前を過ぎたお寿司も取ることが出来ない。
この時、あなたが得られる美味しさの最大の合計値を求めてください。
お寿司は一周回ってくることはないとする。

入力

N
V1 V2 V3...Vn
1行目に、お寿司の数N(1≤N≤1000)が与えられます。
2行目に、お寿司の美味しさ Vi(1≤Vi≤100,1≤i≤N)が半角スペース区切りで与えれれます。

出力

あなたが得られる美味しさの最大の合計値を求めてください。

サンプル

入力例1

4
1 2 3 4

出力例1

6

解説

お寿司の取り方は、「1個目と3個目」のお寿司を取る、「1個目と4個目」のお寿司を取る、または「2個目と4個目」のお寿司を取る方法があるが、 2個目、4個目のお寿司を取ることで、最大の美味しさが得られる。

入力例2

4
5 4 4 9

出力例2

14

入力例3

7
1 2 9 10 1 1 4

出力例3

16