AT_past202306_n 度数分布

There are $ N $ real numbers $ x_1,\ldots,x_N $ between $ 0 $ (inclusive) and $ M $ (exclusive). Among these $ N $ numbers, it is known that there are $ C_k $ numbers between $ k $ (inclusive) and $ k+1 $ (exclusive) for $ k=0,1,\ldots,M-1 $ . You are curious about how small the absolute difference between the median and the mean of $ x_1,\ldots,x_N $ can be. Find the largest $ b $ such that the absolute difference between the median and the mean of $ x_1,\ldots,x_N $ cannot be smaller than $ b $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ C_0 $ $ C_1 $ $ \ldots $ $ C_{M-1} $

Print the answer. Your output will be considered correct if the absolute or relative error from the true answer is at most $ 10^{-6} $ .

### Sample Explanation 1 For example, when $ x_1=1.5, x_2=2, x_3=2.5 $ , the median and the mean of these numbers are both $ 2 $ , and the absolute difference is $ 0 $ . Since the absolute difference cannot be smaller than $ 0 $ , the largest $ b $ such that the absolute difference between the median and the mean cannot be smaller than $ b $ is $ 0 $ . ### Sample Explanation 2 For example, when $ x_1=4, x_2=1-2\times 10^{-100}, x_3=0, x_4=2-2\times 10^{-100} $ , the median is $ 1.5-2\times 10^{-100} $ , the mean is $ 1.75-10^{-100} $ , and the absolute difference is $ 0.25+10^{-100} $ . As seen here, the absolute difference between the median and the mean can be slightly larger than $ 0.25 $ , but we can prove that it cannot be smaller than $ 0.25 $ . Therefore, the answer is $ 0.25 $ . ### Sample Explanation 3 Your output will be considered correct if the absolute or relative error from the true answer is at most $ 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 $ - All input values are integers.