配点 : $300$ 点

問題文

あなたは鍋と $N$ 個の具材を持っています。各具材は 価値 と呼ばれる実数の値を持ち、$i$ 個目 $(1 \leq i \leq N)$ の具材の価値は $v_i$ です。

$2$ 個の具材を鍋に入れると、それらは消滅して新たに $1$ 個の具材が生成されます。この新たな具材の価値は元の $2$ 個の具材の価値を $x, y$ として $(x + y) / 2$ であり、この具材を再び鍋に入れることもできます。

この具材の合成を $N - 1$ 回行うと、最後に $1$ 個の具材が残ります。この具材の価値として考えられる最大の値を求めてください。

制約

• $2 \leq N \leq 50$
• $1 \leq v_i \leq 1000$
• 入力中の値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$v_1$ $v_2$ $\ldots$ $v_N$

出力

最後に残る $1$ 個の具材の価値として考えられる最大の値を表す小数 (または整数) を出力せよ。

出力は、ジャッジの出力との絶対誤差または相対誤差が $10^{-5}$ 以下のとき正解と判定される。

2
3 4

3.5

はじめに持っている具材が $2$ 個の場合、それらをともに鍋に入れるほかありません。価値 $3, 4$ の具材から合成される具材の価値は $(3 + 4) / 2 = 3.5$ です。

なお、3.50001, 3.49999 などと出力しても正解となります。

3
500 300 200

375

今回ははじめに $3$ 個の具材を持っており、一度目の合成で鍋にどの具材を入れるかに選択の余地があります。選択肢は次の $3$ 通りです。

• 価値 $500, 300$ の具材を入れ、価値 $(500 + 300) / 2 = 400$ の具材を合成する。この場合、次の合成ではこれと価値 $200$ の具材を鍋に入れることになり、価値 $(400 + 200) / 2 = 300$ の具材が合成される。
• 価値 $500, 200$ の具材を入れ、価値 $(500 + 200) / 2 = 350$ の具材を合成する。この場合、次の合成ではこれと価値 $300$ の具材を鍋に入れることになり、価値 $(350 + 300) / 2 = 325$ の具材が合成される。
• 価値 $300, 200$ の具材を入れ、価値 $(300 + 200) / 2 = 250$ の具材を合成する。この場合、次の合成ではこれと価値 $500$ の具材を鍋に入れることになり、価値 $(250 + 500) / 2 = 375$ の具材が合成される。

よって、最後に残る $1$ 個の具材の価値として考えられる最大の値は $375$ です。

なお、375.0 などと出力しても正解となります。

5
138 138 138 138 138

138