Border Robot

A high barrier guards a secret laboratory, and N sensors are placed in front of it to identify intruders. The barrier is a straight line, represented by the interval $[0, L]$. Each sensor is a point inside this interval.

All sensors have the same identification range $r$. A sensor at point $p$ can identify intruders in the interval $[p - r, p + r]$. This interval is called the identification interval of the sensor.

One robot is responsible for the boundary of the barrier. It starts at the left end of the barrier. The robot can move left and right along the barrier and carry sensors. It can pick up or drop a sensor only at its own position. The robot can carry any number of sensors at once.

If the union of all identification intervals fully covers the barrier $[0, L]$, the sensors form a perfect boundary. The robot must move sensors when needed to build a perfect boundary. Minimize the total distance the robot travels.

Given the barrier $[0, L]$, the initial positions of N sensors, and the identification range $r$, write a program that prints the minimum total distance the robot must travel to build a perfect boundary.

The first line contains three integers N, L, and r, separated by spaces. They are the number of sensors, the length of the barrier, and the identification range of the sensors.

The second line contains the N initial positions of the sensors, separated by spaces. The positions are given in non-decreasing order, so the list is already sorted.

If no arrangement of the sensors can form a perfect boundary, print -1 on the first line.

Otherwise, print on the first line the minimum total distance the robot must travel to form a perfect boundary. This value is always an integer.

• N is an integer with 1 to 1,000,000.
• L is an integer with 1 to $10^{12}$.
• r is an integer with 1 to $10^{12}$.
• L and r are both integers.
• The initial position of every sensor is an integer from 0 to L, inclusive.
• The initial positions of all sensors are given in non-decreasing order.

In the first example, the robot moves as follows.

1. The robot at 0 moves to 3.
2. It picks up the sensor at its current position.
3. The robot at 3 moves to 2.
4. It drops the carried sensor at its current position.

The final sensor positions are 2 and 6. The union of identification intervals is $[0, 8]$, which fully covers the barrier $[0, 7]$. The robot travels a total distance of 4. No smaller distance can form a perfect boundary, so the answer is 4.

In the second example, the robot moves as follows.

1. It picks up both sensors at position 0.
2. The robot moves from 0 to 1.5.
3. It drops one of the carried sensors at its current position.
4. The robot moves from 1.5 to 7.
5. It drops the remaining sensor at its current position.

Note that the robot can drop sensors at positions that are not integers.