As a cat lover, Xiao B has $n$ cats at home, labeled from $1$ to $n$.
His favorite time of the day is petting his cats, but unfortunately, the cats are not always willing to be petted. The set of cats willing to be petted, $S \subseteq [n]$, is determined randomly according to a probability distribution $P$. After knowing which cats are willing to be petted, Xiao B can choose one cat from the set $S$ to pet. Note that if the set $S$ is empty, Xiao B cannot pet any cat. Xiao B's petting strategy can be randomized. For example, if he knows that cats $1$ and $2$ are both willing to be petted, he can choose to pet the first cat with $50\%$ probability and the second cat with $50\%$ probability.
As a fair person, Xiao B wants to give every cat more opportunities to be petted. He wants to design a petting strategy to maximize the minimum value of $\Pr[i \text{ is petted} | i \in S]$. In other words, let $p_i = \Pr[i \in S]$ be the probability that the $i$-th cat is willing to be petted. We need to design a petting strategy to maximize the constant $c$ such that the probability of each cat being petted is at least $c \cdot p_i$.
Input
The first line contains a positive integer $n$, representing the number of cats.
The next line contains $2^n$ non-negative real numbers, describing a probability distribution $P$. The description is as follows:
Assume $x_i$ is the $i$-th real number. Write $i-1$ in binary form: $i-1 = (a_n a_{n-1} \dots a_1)_2$. Let $T_i = \{j \mid a_j = 1\}$. Then $x_i$ represents the probability that the set of cats willing to be petted is exactly $T_i$.
For example, when $n=2$, we use four non-negative real numbers to describe the probability distribution. The first one represents the probability that no cats are willing to be petted. The second number represents the probability that only the first cat is willing to be petted. The third number represents the probability that only the second cat is willing to be petted. The fourth number represents the probability that both cats are willing to be petted.
It is guaranteed that $x_1 \neq 1$. Due to input precision, it is guaranteed that $1-10^{-6} \le \sum x_i \le 1 + 10^{-6}$.
Output
Output a single real number representing the maximum constant $c$.
Your output is considered correct if and only if the absolute or relative error compared to the standard answer does not exceed $10^{-6}$.
Examples
Input 1
2 0.25 0.25 0.25 0.25
Output 1
0.75
Note 1
In the first example, Xiao B's optimal petting strategy is as follows: when only one cat can be petted, he will definitely pet that cat. When both cats can be petted, he will pet either cat with equal probability.
Therefore, the probability of each cat being petted is $\frac{1}{4} + \frac{1}{4} \times \frac{1}{2} = \frac{3}{8}$. The probability that each cat is willing to be petted is $\frac{1}{4} + \frac{1}{4} = \frac{1}{2}$. Thus, the optimal constant $c = \frac{3}{8} / 0.5 = \frac{3}{4}$.
Input 2
3 0.12 0.18 0.02 0.1 0.1 0.05 0.15 0.28
Output 2
0.5057471264
Subtasks
Note that the input size for this problem is large. We guarantee that the standard solution uses scanf to read all numbers, and the time spent on reading input by the standard solution does not exceed $250$ ms.
Subtask 1 [12 pts]: $1 \le n \le 2$.
Subtask 2 [18 pts]: $1 \le n \le 7$.
Subtask 3 [10 pts]: $1 \le n \le 10$.
Subtask 4 [35 pts]: $1 \le n \le 15$.
Subtask 5 [25 pts]: $1 \le n \le 20$.