CF596D.Wilbur and Trees

Wilbur the pig really wants to be a beaver, so he decided today to pretend he is a beaver and bite at trees to cut them down.

There are n trees located at various positions on a line. Tree i is located at position x__i. All the given positions of the trees are distinct.

The trees are equal, i.e. each tree has height h. Due to the wind, when a tree is cut down, it either falls left with probability p, or falls right with probability 1 - p. If a tree hits another tree while falling, that tree will fall in the same direction as the tree that hit it. A tree can hit another tree only if the distance between them is strictly less than h.

For example, imagine there are 4 trees located at positions 1, 3, 5 and 8, while h = 3 and the tree at position 1 falls right. It hits the tree at position 3 and it starts to fall too. In it's turn it hits the tree at position 5 and it also starts to fall. The distance between 8 and 5 is exactly 3, so the tree at position 8 will not fall.

As long as there are still trees standing, Wilbur will select either the leftmost standing tree with probability 0.5 or the rightmost standing tree with probability 0.5. Selected tree is then cut down. If there is only one tree remaining, Wilbur always selects it. As the ground is covered with grass, Wilbur wants to know the expected total length of the ground covered with fallen trees after he cuts them all down because he is concerned about his grass-eating cow friends. Please help Wilbur.

小猪威尔伯非常想成为一只海狸，因此他决定今天假装自己是海狸，通过啃咬树木来砍倒它们。

一条直线上分布着 $n$ 棵树。第 $i$ 棵树位于位置 $x_i$。所有给定的树的位置互不相同。

所有树完全相同，即每棵树的高度均为 $h$。由于风的影响，当一棵树被砍倒时，它以概率 $p$ 向左倾倒，以概率 $1 - p$ 向右倾倒。若一棵倒下的树在倾倒过程中撞到了另一棵仍站立的树，则被撞的树也将朝相同方向倾倒。一棵树仅当与另一棵树的距离严格小于 $h$ 时，才可能撞到它。

例如，假设有 4 棵树分别位于位置 $1$、$3$、$5$ 和 $8$，且 $h = 3$，而位于位置 $1$ 的树向右倾倒。它将撞到位于位置 $3$ 的树，使其也开始向右倾倒；该树继而又撞到位于位置 $5$ 的树，使其也向右倾倒。而位置 $8$ 与位置 $5$ 之间的距离恰好为 $3$，因此位于位置 $8$ 的树不会倾倒。

只要仍有树处于站立状态，威尔伯就会以 $0.5$ 的概率选择最左侧的站立树，或以 $0.5$ 的概率选择最右侧的站立树，并将其砍倒。若仅剩一棵树，则威尔伯总是选择它。

由于地面覆盖着青草，威尔伯想知道：在他砍倒所有树后，倒伏树木所覆盖的地面总长度的期望值是多少？他很关心自己那些吃草的牛朋友们。请帮助威尔伯。

The first line of the input contains two integers, n (1 ≤ n ≤ 2000) and h (1 ≤ h ≤ 108) and a real number p (0 ≤ p ≤ 1), given with no more than six decimal places.

The second line of the input contains n integers, _x_1, _x_2, ..., x__n ( - 108 ≤ x__i ≤ 108) in no particular order.

输入的第一行包含两个整数 $n$（$1 \leq n \leq 2000$）和 $h$（$1 \leq h \leq 10^8$），以及一个实数 $p$（$0 \leq p \leq 1$），$p$ 最多保留六位小数。

输入的第二行包含 $n$ 个整数 $x_1,\,x_2,\,\dots,\,x_n$（$-10^8 \leq x_i \leq 10^8$），它们以任意顺序给出。

Print a single real number — the expected total length of the ground covered by trees when they have all fallen down. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if .

输出一个实数——所有树倒下后覆盖地面的总长度的期望值。若你的答案的绝对或相对误差不超过 $10^{-6}$，则视为正确。

即：假设你的答案为 $a$，评测组的答案为 $b$。当且仅当 时，评测程序将判定你的答案正确。

Consider the first example, we have 2 trees with height 2.

There are 3 scenarios:

1. Both trees falls left. This can either happen with the right tree falling left first, which has probability (also knocking down the left tree), or the left tree can fall left and then the right tree can fall left, which has probability. Total probability is .

2. Both trees fall right. This is analogous to (1), so the probability of this happening is .

3. The left tree fall left and the right tree falls right. This is the only remaining scenario so it must have probability.

Cases 1 and 2 lead to a total of 3 units of ground covered, while case 3 leads to a total of 4 units of ground covered. Thus, the expected value is .

考虑第一个例子，我们有 2 棵高度为 2 的树。

共有 3 种情形：

1. 两棵树均向左倒。这可能以两种方式发生：

   • 右侧的树先向左倒，其概率为 （同时会撞倒左侧的树）；
   • 或左侧的树先向左倒，随后右侧的树再向左倒，其概率为 。
     总概率为 。

2. 两棵树均向右倒。该情形与情形 (1) 对称，因此发生的概率为 。

3. 左侧的树向左倒，右侧的树向右倒。这是唯一剩余的情形，因此其概率必为 。

情形 1 和情形 2 均导致总共覆盖 3 单位地面，而情形 3 导致总共覆盖 4 单位地面。因此，期望值为 。