004 - Swith Roler

問題

メリークリスマス！！　ということで、n個のスイスロールを一列に並べました。しかしei1929は魔法の粉（原材料：カカオ１００%）を持っていて、スイスロールにかけることでブッシュ・ド・ノエル（以下ノエル）に早変わりするのです。スイスロールiのおいしさをa_iとすると、粉をかけることでおいしさが(10000 - a_i)になります。 それだけならいいのですが、ei1929は几帳面なので、ノエル同士の間にスイスロールが、スイスロール同士の間にノエルが存在してはいけません。つまり任意の数j(1≦j＜n)とすると、1からj番目、もしくはjからn番目までにはスイスロールだけがあり、その他はノエルとなります。その上、並び替えずに双方が必ず存在するようしてほしいのです（ほしがりだね）。この条件で得られる最大のおいしさを求めてください（よくばりだね）。

入力

n
a1
a2
…
an

１行目にスイスロールの個数nが与えられます。 ２行目から2+n行目にかけて、スイスロールi(1≦i≦n)のおいしさが与えられます。

出力

条件を満たした状態で得られる最大のおいしさを出力してください。

制約

全ての入出力ケースで以下を満たします。

• 2　≦　n　≦　10⁵
• 1　≦　a_i　≦　9999

入出力例

入力例1

3
5000
1000
2000

出力例1

22000

スイスロール2,3をノエルにします。そうすることでそれぞれのおいしさは、9000,8000となります。スイスロール1はノエルにしてもおいしさは同じですが、スイスロールとノエルの両方がないといけないのでスイスロールのままにします。これが最大です。

入力例2

4
1000
9000
8000
3000

出力例2

29000

ノエルに変えたときのほうがおいしさが大きくなるものは、スイスロール1,4です。しかし両方とも変化させるとスイスロール2,3を挟み込んでしまいます。なのでより多くの幸せが得られるように1だけノエルにします。