The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

binary search

math

two pointers

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Morning run

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPeople 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.

Input

The first line of the input contains three integers *n*, *l*, *t* (1 ≤ *n* ≤ 10^{6}, 1 ≤ *l* ≤ 10^{9}, 1 ≤ *t* ≤ 10^{9}). 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.

Output

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

Examples

Input

2 5 1

0 2

Output

0.2500000000

Input

3 7 3

0 1 6

Output

1.5000000000

Note

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/18/2024 10:38:53 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|