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

時間制限 2 秒 / メモリ制限 512 MB / 得点 100 / x 0 /


TLE
2sec
MLE
512MB
得点
100

問題

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


図 1: ケーキの例 (N = 5, A1 = 2, A2 = 8, A3 = 1, A4 = 10, A5 = 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 ≤ iN) には整数 Ai が書かれており,i 番目のピースの大きさが Ai であることを表す.

出力

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

制限

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

  • 1 ≤ N ≤ 2 000.
  • 1 ≤ Ai ≤ 1 000 000 000.
  • Ai はすべて異なる.

小課題

小課題 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