Flip n fair coins, then repeatedly throw away one head together with one tail until you cannot any more. Return the expected number of coins left over.

Whatever order you remove them in, what survives is the imbalance: if H heads came up, exactly $|H - (n - H)|$ coins remain. So you want

$$E\bigl[\,|2H - n|\,\bigr], \qquad H \sim \mathrm{Binomial}(n, 1/2)$$

Input

10

Output

2.4609375