Time Limit: 2 sec / Memory Limit: 512 MB
配点: 100 点
JOI くんと IOI ちゃんは双子の兄妹である.JOI くんは最近お菓子作りに凝っていて,今日も JOI くんはケーキを焼いて食べようとしたのだが,焼きあがったところで匂いをかぎつけた IOI ちゃんが来たので 2 人でケーキを分けることになった.
ケーキは円形である.ある点から放射状に切り目を入れ,ケーキを N 個のピースに切り分け,ピースに 1 から N まで反時計回りに番号をつけた.つまり,1 \leqq i \leqq N に対し,i 番目のピースは i - 1 番目と i + 1 番目のピースと隣接している (ただし 0 番目は N 番目,N + 1 番目は 1 番目とみなす).i 番目のピースの大きさは A_i だったが,切り方がとても下手だったので A_i はすべて異なる値になった.
図 1: ケーキの例 (N = 5,A_1 = 2,A_2 = 8,A_3 = 1,A_4 = 10,A_5 = 9)
この N 個を JOI くんと IOI ちゃんで分けることにした.分け方は次のようにすることにした:
- まず JOI くんが N 個のうちの好きな 1 つを選んで取る.
- その後,IOI ちゃんからはじめて IOI ちゃんと JOI くんが交互に残りのピースを 1 つずつ取っていく.ただし,両隣のピースのうち少なくとも一方が既に取られているようなピースしか取ることができず,取れるピースが複数あるときは,IOI ちゃんはそのうち最も大きいものを選んで取り,JOI くんはそのうちで好きなものを選んで取ることができる.
JOI くんは,自分が最終的に取るピースの大きさの合計を最大化したい.
課題
ケーキのピースの数 N と,N 個のピースの大きさの情報が与えられたとき,JOI くんが取れるピースの大きさの合計の最大値を求めるプログラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
- 1 行目には整数 N が書かれており,ケーキが N 個のピースに切り分けられていることを表す.
- 続く N 行のうちの i 行目 (1 \leqq i \leqq N) には整数 A_i が書かれており,i 番目のピースの大きさが A_i であることを表す.
出力
標準出力に,JOI くんが取れるピースの大きさの合計の最大値を表す整数を 1 行で出力せよ.
制限
すべての入力データは以下の条件を満たす.
- 1 \leqq N \leqq 2\,000.
- 1 \leqq A_i \leqq 1\,000\,000\,000.
- A_i はすべて異なる.
小課題
小課題 1 [15 点]
- N \leqq 20 を満たす.
小課題 2 [45 点]
- N \leqq 300 を満たす.
小課題 3 [40 点]
追加の制限はない.
入力例 1
5 2 8 1 10 9
出力例 1
18
JOI くんは,次のようにピースを取るのが最適である.
- JOI くんは 2 番目のピースを取る.このピースの大きさは 8 である.
- IOI ちゃんは 1 番目のピースを取る.このピースの大きさは 2 である.
- JOI くんは 5 番目のピースを取る.このピースの大きさは 9 である.
- IOI ちゃんは 4 番目のピースを取る.このピースの大きさは 10 である.
- 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