0269 - ケーキの切り分け２ (Cake 2)

問題

　JOI くんと IOI ちゃんは双子の兄妹である．JOI くんは最近お菓子作りに凝っていて，今日も JOI くんはケーキを焼いて食べようとしたのだが，焼きあがったところで匂いをかぎつけた IOI ちゃんが来たので 2 人でケーキを分けることになった．
　ケーキは円形である．ある点から放射状に切り目を入れ，ケーキを N 個のピースに切り分け，ピースに 1 から N まで反時計回りに番号をつけた．つまり，1 ≤ i ≤ N に対し，i 番目のピースは i - 1 番目と i + 1 番目のピースと隣接している (ただし 0 番目は N 番目，N + 1 番目は 1 番目とみなす) ．i 番目のピースの大きさは A_i だったが，切り方がとても下手だったので A_i はすべて異なる値になった．

図 1: ケーキの例 (N = 5, A₁ = 2, A₂ = 8, A₃ = 1, A₄ = 10, A₅ = 9)

この N 個を JOI くんと IOI ちゃんで分けることにした．分け方は次のようにすることにした：

1. まず JOI くんが N 個のうちの好きな 1 つを選んで取る．
2. その後，IOI ちゃんからはじめて IOI ちゃんと JOI くんが交互に残りのピースを 1 つずつ取っていく．ただし，両隣のピースのうち少なくとも一方が既に取られているようなピースしか取ることができず，取れるピースが複数あるときは，IOI ちゃんはそのうち最も大きいものを選んで取り，JOI くんはそのうちで好きなものを選んで取ることができる．

JOI くんは，自分が最終的に取るピースの大きさの合計を最大化したい．

課題

　ケーキのピースの数 N と，N 個のピースの大きさの情報が与えられたとき，JOI くんが取れるピースの大きさの合計の最大値を求めるプログラムを作成せよ．

入力

　標準入力から以下の入力を読み込め．

• 1 行目には整数 N が書かれており，ケーキが N 個のピースに切り分けられていることを表す．
• 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には整数 A_i が書かれており，i 番目のピースの大きさが A_i であることを表す．

出力

　標準出力に，JOI くんが取れるピースの大きさの合計の最大値を表す整数を 1 行で出力せよ．

制限

　すべての入力データは以下の条件を満たす．

• 1 ≤ N ≤ 2 000．
• 1 ≤ A_i ≤ 1 000 000 000．
• A_i はすべて異なる．

小課題

小課題 1 [15 点]

• N ≤ 20 を満たす．

小課題 2 [45 点]

• N ≤ 300 を満たす．

小課題 3 [40 点]

追加の制限はない．

入出力例

入力例 1

5
2
8
1
10
9

出力例 1

18

JOI くんは，次のようにピースを取るのが最適である．

1. JOI くんは 2 番目のピースを取る．このピースの大きさは 8 である．
2. IOI ちゃんは 1 番目のピースを取る．このピースの大きさは 2 である．
3. JOI くんは 5 番目のピースを取る．このピースの大きさは 9 である．
4. IOI ちゃんは 4 番目のピースを取る．このピースの大きさは 10 である．
5. JOI くんは 3 番目のピースを取る．このピースの大きさは 1 である．

最終的に，JOI くんが取ったピースの大きさの合計は，8 + 9 + 1 = 18 となる．

入力例 2

8
1
10
4
5
6
2
9
3

出力例 2

26

入力例 3

15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789

出力例 3

3600242976