There are `n` balls, where the `i`-th ball is labeled as `p`_{i}. You are going to put `n` balls into a deque. In the `i`-th turn, you need to put the `i`-th ball to the deque. Each ball will be put to both ends of the deque with equal probability.

Let the sequence (`x`_{1}, `x`_{2}, ..., `x`_{n}) be the labels of the balls in the deque from left to right. The beauty of the deque `B`(`x`_{1}, `x`_{2}, ..., `x`_{n}) is defined as the number of descents in the sequence. For the sequence (`x`_{1}, `x`_{2}, ..., `x`_{n}), a descent is a position `i` (1 ≤ `i` < `n`) with `x`_{i} > `x`_{i+1}.

You need to find the expected value of `B`(`x`_{1}, `x`_{2}, ..., `x`_{n}).

Deque is a double-ended queue for which elements can be added to or removed from either the front (head) or the back (tail).