JOI くんと IOI ちゃんのケーキの分け方

JOI くんと IOI ちゃんは双子の兄妹です。JOI くんは最近お菓子作りに凝っていて、今日も JOI くんはケーキを焼いて食べようとしましたが、焼きあがったところで匂いをかぎつけた IOI ちゃんが来たので2人でケーキを分けることになりました。

ケーキは円形です。ある点から放射状に切り目を入れ、ケーキをN個のピースに切り分け、ピースに1からNまで反時計回りに番号をつけます。つまり、1 ≤ i ≤ N に対し、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 ≤ i ≤ N) には整数Aiが書かれており、i番目のピースの大きさがAiであることを表します。

出力

標準出力に、JOI くんが取れるピースの大きさの合計の最大値を表す整数を1行で出力してください。

---

制限

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

• 1 ≤ N ≤ 2000.
• 1 ≤ Ai ≤ 1000000000.
• Aiはすべて異なる値です。

---

入力例 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