Problem Statement

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$.

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.

Sample Input 1Copy

3 3
0 1 2

Sample Output 1Copy

0.0

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 Input 2Copy

4 5
2 1 0 0 1

Sample Output 2Copy

0.25

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 Input 3Copy

10 10
1 0 0 0 0 0 0 0 0 9

Sample Output 3Copy

0.4

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