CF309A.Morning run

People like to be fit. That's why many of them are ready to wake up at dawn, go to the stadium and run. In this problem your task is to help a company design a new stadium.

The city of N has a shabby old stadium. Many people like it and every morning thousands of people come out to this stadium to run. The stadium can be represented as a circle, its length is exactly l meters with a marked start line. However, there can't be simultaneous start in the morning, so exactly at 7, each runner goes to his favorite spot on the stadium and starts running from there. Note that not everybody runs in the same manner as everybody else. Some people run in the clockwise direction, some of them run in the counter-clockwise direction. It mostly depends on the runner's mood in the morning, so you can assume that each running direction is equiprobable for each runner in any fixed morning.

The stadium is tiny and is in need of major repair, for right now there only is one running track! You can't get too playful on a single track, that's why all runners keep the same running speed — exactly 1 meter per a time unit. Nevertheless, the runners that choose different directions bump into each other as they meet.

The company wants to design a new stadium, but they first need to know how bad the old one is. For that they need the expectation of the number of bumpings by t time units after the running has begun. Help the company count the required expectation. Note that each runner chooses a direction equiprobably, independently from the others and then all runners start running simultaneously at 7 a.m. Assume that each runner runs for t time units without stopping. Consider the runners to bump at a certain moment if at that moment they found themselves at the same point in the stadium. A pair of runners can bump more than once.

人们喜欢保持健康。正因如此，许多人愿意在黎明时分起床，前往体育场跑步。本题中，你的任务是帮助一家公司设计一座新体育场。

N 市拥有一座破旧的老体育场。许多人喜爱它，每天清晨成千上万的人来到这座体育场跑步。该体育场可建模为一个圆，其周长恰好为 $l$ 米，并标有起跑线。然而，清晨无法实现同时起跑，因此每天早上 7 点整，每位跑步者都会前往自己在体育场中最钟爱的位置，并从该处开始跑步。注意，并非所有人的跑步方式都相同：有些人顺时针跑，有些人逆时针跑。这主要取决于跑步者清晨的心情，因此你可以假设：在任意一个固定的早晨，对每一位跑步者而言，两种跑步方向出现的概率相等。

该体育场规模狭小，亟需大规模修缮；目前仅有一条跑道！在单条跑道上无法过于随意，因此所有跑步者均保持相同的跑步速度——恰好为每单位时间 $1$ 米。尽管如此，选择不同方向的跑步者在相遇时仍会发生碰撞。

该公司希望设计一座新体育场，但首先需要了解旧体育场的问题严重程度。为此，他们需要计算：从开始跑步起经过 $t$ 个时间单位后，发生碰撞的期望次数。请帮助该公司计算这一所需期望值。注意：每位跑步者独立地、以相等概率选择跑步方向，随后所有跑步者于上午 7 点整同时起跑。假设每位跑步者持续跑步 $t$ 个时间单位且中途不停止。若在某一时刻，两名跑步者恰好位于体育场的同一位置，则称他们在该时刻发生了一次碰撞。一对跑步者可能多次发生碰撞。

The first line of the input contains three integers n, l, t (1 ≤ n ≤ 106, 1 ≤ l ≤ 109, 1 ≤ t ≤ 109). The next line contains n distinct integers _a_1, _a_2, ..., a__n (0 ≤ _a_1 < _a_2 < ... < a__n < l), here a__i is the clockwise distance from the start line to the i-th runner's starting position.

输入的第一行包含三个整数 $n$、$l$、$t$（$1 ≤ n ≤ 10^6$，$1 ≤ l ≤ 10^9$，$1 ≤ t ≤ 10^9$）。下一行包含 $n$ 个互不相同的整数 $a_1,\,a_2,\,...,\,a_n$（$0 ≤ a_1 < a_2 < ... < a_n < l$），其中 $a_i$ 表示第 $i$ 名选手起跑位置顺时针方向距起跑线的距离。

Print a single real number — the answer to the problem with absolute or relative error of at most 10 - 6.

输出一个实数——该问题的答案，其绝对或相对误差不超过 $10^{-6}$。

There are two runners in the first example. If the first runner run clockwise direction, then in 1 time unit he will be 1m away from the start line. If the second runner run counter-clockwise direction then in 1 time unit he will be also 1m away from the start line. And it is the only possible way to meet. We assume that each running direction is equiprobable, so the answer for the example is equal to 0.5·0.5 = 0.25.

第一个样例中有两名跑步者。如果第一名跑步者沿顺时针方向奔跑，则在 1 个时间单位后，他将距离起跑线 1 米；如果第二名跑步者沿逆时针方向奔跑，则在 1 个时间单位后，他也恰好距离起跑线 1 米。这是两人相遇的唯一可能方式。我们假设每位跑步者的奔跑方向是等概率的，因此该样例的答案为 $0.5 \cdot 0.5 = 0.25$。