Auf einem Kreis stehen $N$ Roboter. Die nördlichste Position erhält die Nummer $0$. Der Kreis wird in $M$ gleiche Teile geteilt ($M \ge N$), und die übrigen Teilungspunkte werden im Uhrzeigersinn von $1$ bis $M-1$ nummeriert. So entstehen die Positionen $0$ bis $M-1$ (Abbildung 1). Anfangs stehen die Roboter auf $N$ verschiedenen Positionen.

Der Abstand zwischen zwei Positionen $x,y$ ist als $y-x$ definiert ($y \ge x$). Ein Roboter $R_i$ auf Position $x_i$ kann Punkte innerhalb einer festen Reichweite $R>0$ in beiden Richtungen überwachen. Ist $a$ die Position im Abstand $R$ gegen den Uhrzeigersinn von $x_i$ und $b$ die Position im Abstand $R$ im Uhrzeigersinn, überwacht $R_i$ den im Uhrzeigersinn von $a$ nach $b$ verlaufenden Teil des Kreises.

Wir möchten den gesamten Kreis überwachen. Bei der anfänglichen Aufstellung können Teile unüberwacht bleiben; dann sollen die Roboter so bewegt werden, dass sie den gesamten Kreis abdecken. Wir nehmen $M \le 2RN$ an, wodurch eine solche Bewegung stets möglich ist.

Roboter dürfen nur zu den oben definierten Kreispositionen bewegt werden, und jeder Roboter darf höchstens einmal bewegt werden. Der größte von einem Roboter zurückgelegte Weg soll minimiert werden.

In Abbildung 1 stehen beispielsweise drei Roboter $R_1,R_2,R_3$ auf den Positionen $1,2,5$, und ihre Reichweite ist $R=2$. Um den gesamten Kreis zu überwachen, bewegt sich $R_1$ auf Position $0$ und $R_3$ auf Position $6$. Diese Bewegung minimiert den größten zurückgelegten Weg.

Abbildung 1

Gegeben sind die Positionen von $N$ Robotern, ihre Reichweite $R$ und die ganze Zahl $M$. Bestimme und gib den kleinstmöglichen maximalen Bewegungsweg aus, mit dem die Roboter den gesamten Kreis überwachen können.

Eingabe

Die Standardeingabe enthält Folgendes. Die erste Zeile enthält die Roboteranzahl $N$ ($1 \le N \le 1,000,000$). Die zweite enthält zwei ganze Zahlen $R,M$, welche die Reichweite und die Kreispositionen definieren ($1 \le R,M \le 10^9$, $N \le M \le 2RN$). Die nächste Zeile enthält $N$ verschiedene ganze Zahlen $x_i$ ($0 \le x_i \le M-1$, $i=1,\ldots,N$), durch Leerzeichen getrennt, als Anfangspositionen der Roboter.

Teilaufgaben

• Teilaufgabe 1: 10 von 100 Punkten; $M \le 10$.

• Teilaufgabe 2: 30 von 100 Punkten; $N \le 7,000$.

• Teilaufgabe 3: 60 von 100 Punkten; keine zusätzlichen Beschränkungen.

Ausgabe

Gib auf der Standardausgabe den kleinstmöglichen maximalen Bewegungsweg der Roboter aus, mit dem der gesamte Kreis überwacht wird.

Beispiele

Eingabe 1

3
2 10
1 2 5

Ausgabe 1

1

Eingabe 2

6
1 11
0 1 2 3 4 5

Ausgabe 2

2