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 ちゃんで分けることにした．分け方は次のようにすることにした：

1. まず JOI くんが $N$ 個のうちの好きな $1$ つを選んで取る．
2. その後，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 くんは，次のようにピースを取るのが最適である．

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