There are $N$ robots on a circle. The northernmost position is numbered $0$. Divide the circle into $M$ equal parts ($M \ge N$) and number the remaining division points $1$ through $M-1$ clockwise. This defines positions $0$ through $M-1$ on the circle (Figure 1). Initially, the robots occupy $N$ distinct positions.

The distance between two positions $x$ and $y$ on the circle is defined as $y-x$ ($y \ge x$). A robot $R_i$ at position $x_i$ can monitor points within a fixed range $R>0$ in both counterclockwise and clockwise directions. In other words, if $a$ is the position at distance $R$ counterclockwise from $x_i$, and $b$ is the position at distance $R$ clockwise from $x_i$, then robot $R_i$ can monitor the clockwise part of the circle from $a$ to $b$.

We want to monitor the entire circle. Some parts may not be monitored from the robots’ initial positions, so in that case we want to move the robots to cover the entire circle. We assume $M \le 2RN$, which ensures that a movement of robots covering the entire circle can always be found.

When moved, robots may only move to the positions on the circle defined above, and each robot may move at most once. We want to minimize the maximum distance moved by any robot.

For example, in Figure 1 below, three robots $R_1,R_2,R_3$ are at positions $1,2,5$, respectively, and their monitoring range is $R=2$. To monitor the entire circle, robot $R_1$ moves to position $0$ and robot $R_3$ moves to position $6$. This movement minimizes the maximum distance moved by the robots.

Figure 1

Given the positions of $N$ robots, their range $R$, and integer $M$, find and print the minimum possible maximum distance moved when moving the robots to monitor the entire circle.

Input

The following information is given on standard input. The first line contains the number of robots $N$ ($1 \le N \le 1,000,000$). The second line contains two integers $R$ and $M$, defining the monitoring range and the positions on the circle ($1 \le R,M \le 10^9$, $N \le M \le 2RN$). The next line contains $N$ distinct integers $x_i$ ($0 \le x_i \le M-1$, $i=1,\ldots,N$), separated by spaces, giving the initial robot positions.

Subtasks

• Subtask 1: 10 points out of 100; $M \le 10$.

• Subtask 2: 30 points out of 100; $N \le 7,000$.

• Subtask 3: 60 points out of 100; no constraints beyond the original constraints.

Output

Print to standard output the minimum possible maximum distance moved by the robots so that the entire circle is monitored.

Examples

Input 1

3
2 10
1 2 5

Output 1

1

Input 2

6
1 11
0 1 2 3 4 5

Output 2

2