Problem G
One Below

Number Game. Source: wordclouds.com.

Two mathematicians play the following zero-sum game. They independently write a positive integer on a paper slip, then compare the integers they wrote down. If they both wrote the same number, it’s a tie. If one wrote a number that’s smaller than the number written down by the other, they will win $1$ point unless the number they wrote was smaller by $1$, in which case the other player will win $2$ points. For instance, if Player One writes $1$ and Player Two writes $3$, Player One will win $1$ point. If Player One had written $4$, Player Two would have lost $2$ points instead.

Clearly, to be successful at this game, no player can use a deterministic strategy - if they did and their opponent found out, they could always find an integer to counter the integer chosen by this strategy and win. Therefore, Player One will play a randomized strategy, drawing positive integers from $1, 2, 3, \ldots $ with some probability $p_i$.

You are Player Two and you have learned Player One’s randomized strategy. Determine the optimal counterstrategy that maximizes the expected value of Player Two’s winnings. Since the game is fair, note that if Player One plays an optimal strategy, Player Two’s expected value will be zero.

Input

The input consists of two lines. The first line contains an integer $n$ ($1 \le n \le 20$) denoting the maximum $n$ for which $p_n$ is non-zero. That is, Player One will never play a number that is greater than $n$. The second line contains $n$ real numbers $p_i$ ($0 \le p_i \le 1, i = 1 \ldots n$), given with at most $8$ digits after the decimal point. You are guaranteed that the different values of $p_i$ sum up to $1$, i.e., $\sum _{i=1}^n p_i = 1$.

Output

Output $2$ lines. The first line shall contain two numbers. The first number is the maximum expected win (in points) for Player Two, assuming Player Two plays an optimal strategy. The second number, $m$ is the highest index such that $q_m$ is non-zero, assuming that the optimal strategy involves playing numbers $1, 2, 3, \ldots , m$ with probability $q_1, q_2, q_3, \ldots , q_m$. On the second line, output $m$ real numbers which denote the probabilities $q_i$. Your answer will be accepted if your probability distribution yields the expected win you output on line $1$ and if it matches the actual optimal value. The absolute error in both cases must be less or equal than $10^{-5}$. If more than one strategy maximizes Player Two’s gains, you may output any of them.

1
1.0

2.0 2
0 1

2
0.0 1.0

2.0 3
0 0 1

10
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.5 0.5

1.0 10
0 0 0 0 0 0 0 0 0 1

5
0.0625 0.3125 0.25 0.3125 0.0625

0.0 5
0.2 0.2 0.2 0.2 0.2

4
0.3 0.3 0.3 0.1

0.1 3
0 0.4 0.6