P15817 [JOI 2015 Final] ケーキの切り分け２

JOI くんと IOI ちゃんは双子の兄妹である．JOI くんは最近お菓子作りに凝っていて，今日も JOI くんはケーキを焼いて食べようとしたのだが，焼きあがったところで匂いをかぎつけた IOI ちゃんが来たので 2 人でケーキを分けることになった． ケーキは円形である．ある点から放射状に切り目を入れ，ケーキを $N$ 個のピースに切り分け，ピースに 1 から $N$ まで反時計回りに番号をつけていた．つまり，$1 \le i \le N$ に対し，$i$ 番目のピースは $i-1$ 番目と $i+1$ 番目のピースと隣接している（ただし 0 番目は $N$ 番目，$N+1$ 番目は 1 番目とみなす）．$i$ 番目のピースの大きさは $A_i$ だったが，切り方がとても下手だったので $A_i$ はすべて異なる値になった． :::align{center}  図 1: ケーキの例 ($N = 5, A_1 = 2, A_2 = 8, A_3 = 1, A_4 = 10, A_5 = 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 \le i \le N$) には整数 $A_i$ が書かれており，$i$ 番目のピースの大きさが $A_i$ であることを表す．

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

### 入出力例 1 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$ となる． ### 制限 すべての入力データは以下の条件を満たす． - $1 \le N \le 2000$． - $1 \le A_i \le 1000000000$． - $A_i$ はすべて異なる． ### 小課題 #### 小課題 1 [15 点] - $N \le 20$ を満たす． #### 小課題 2 [45 点] - $N \le 300$ を満たす． #### 小課題 3 [40 点] 追加の制限はない．