AT_past202306_n 度数分布

$ 0 $ 以上 $ M $ 未満の $ N $ 個の実数 $ x_1,\ldots,x_N $ があります。 これら $ N $ 個のうち、値が $ k $ 以上 $ k+1 $ 未満であるようなものが $ C_k $ 個あることがわかっています $ (k=0,1,\ldots,M-1) $ 。 あなたは、 $ x_1,\ldots,x_N $ の中央値と平均値の差の絶対値がどのくらい小さくなるか気になりました。 「 $ x_1,\ldots,x_N $ の中央値と平均値の差の絶対値は $ b $ 未満にならない」と言えるような最大の $ b $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ C_0 $ $ C_1 $ $ \ldots $ $ C_{M-1} $

答えを出力せよ。 なお、真の解との絶対誤差または相対誤差が $ 10^{-6} $ 以下であれば正解として扱われる。

### Sample Explanation 1 例えば $ x_1=1.5, x_2=2, x_3=2.5 $ のとき、これらの中央値と平均値はともに $ 2 $ になり、差の絶対値は $ 0 $ となります。 絶対値が $ 0 $ 未満になることはないので、「中央値と平均値の差の絶対値は $ b $ 未満にならない」と言えるような最大の $ b $ は $ 0 $ となります。 ### Sample Explanation 2 例えば $ x_1=4, x_2=1-2\times 10^{-100}, x_3=0, x_4=2-2\times 10^{-100} $ のとき、これらの中央値は $ 1.5-2\times 10^{-100} $ 、平均値は $ 1.75-10^{-100} $ となり、差の絶対値は $ 0.25+10^{-100} $ となります。 このように中央値と平均値の差の絶対値として $ 0.25 $ よりわずかに大きな値はありえますが、 $ 0.25 $ 未満にはならないことが証明できます。よって答えは $ 0.25 $ となります。 ### Sample Explanation 3 真の解との絶対誤差または相対誤差が $ 10^{-6} $ 以下であれば正解となります。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq M \leq 2 \times 10^5 $ - $ 0 \leq C_k $ - $ C_0+\ldots+C_{M-1}=N $ - 入力は全て整数である