問題文

一列に並んだ$N$人のプログラマーがいます。左から$i$番目のプログラマーのやる気は$A_i$です。
まず正の数$K$を決めます。
次の操作を任意の回数繰り返して$K$人ずつのチームをいくつか作ります。

・プログラマーが$K$人以上残っているとき、左あるいは右の端から連続する$K$人のプログラマーを取り除く。この取り除いた$K$人を1つのチームとする。

ここで$K$は一度操作を始めた後変えることはできません。
1つのチームの行動力は$K$×(チーム内におけるプログラマーのやる気の中央値)となります。
やる気の中央値とは、チームのプログラマーのやる気を昇順にソートした列を$B_1,B_2, \dots\ B_K$とすると、$K$が偶数の時$B_{K/2}$、$K$が奇数の時$B_{(K+1)/2}$のことです。

適切に$K$を選び最適にチームを作った時の、行動力の総和の最大値を求めてください。
ただしチームを全く作らなかった時の行動力は$0$とします。

入力

$N$
$A_{1}\ A_{2}\ \dots\ A_{N}$

入力は全て整数である
$1 \le N \le 10^4$
$-10^9 \le A_i \le 10^9 (1 \le i \le N)$

出力

最後に改行してください。

サンプル

3
1 -1 2

3

10
-1 2 -3 4 -5 6 -7 8 -9 10

33

20
2 3 4 5 -120 -6 7 8 9 11 38 -21 34 22 2 11 10 -90 -20 -10

165