Na okręgu znajduje się $N$ robotów. Najbardziej wysunięta na północ pozycja ma numer $0$. Dzielimy okrąg na $M$ równych części ($M \ge N$) i numerujemy pozostałe punkty podziału od $1$ do $M-1$ zgodnie z ruchem wskazówek zegara. Otrzymujemy pozycje od $0$ do $M-1$ (rysunek 1). Początkowo roboty zajmują $N$ różnych pozycji.

Odległość między dwiema pozycjami $x,y$ na okręgu definiujemy jako $y-x$ ($y \ge x$). Robot $R_i$ na pozycji $x_i$ może obserwować punkty w ustalonym zasięgu $R>0$ w obu kierunkach. Jeśli $a$ jest pozycją w odległości $R$ od $x_i$ przeciwnie do ruchu wskazówek zegara, a $b$ w odległości $R$ zgodnie z tym ruchem, robot $R_i$ obserwuje część okręgu od $a$ do $b$ zgodnie z ruchem wskazówek zegara.

Chcemy obserwować cały okrąg. Początkowe pozycje mogą pozostawiać nieobserwowane części, więc chcemy przesunąć roboty tak, by objąć cały okrąg. Zakładamy $M \le 2RN$, co gwarantuje istnienie takiego przemieszczenia.

Roboty mogą przemieszczać się tylko na zdefiniowane powyżej pozycje na okręgu, a każdy robot może przemieścić się co najwyżej raz. Chcemy zminimalizować największą odległość pokonaną przez dowolnego robota.

Na przykład na rysunku 1 trzy roboty $R_1,R_2,R_3$ znajdują się odpowiednio na pozycjach $1,2,5$, a ich zasięg wynosi $R=2$. Aby obserwować cały okrąg, robot $R_1$ przechodzi na pozycję $0$, a robot $R_3$ na pozycję $6$. To przemieszczenie minimalizuje największą pokonaną odległość.

Rysunek 1

Dane są pozycje $N$ robotów, zasięg $R$ i liczba całkowita $M$. Znajdź i wypisz najmniejszą możliwą maksymalną odległość przemieszczenia robotów, pozwalającą obserwować cały okrąg.

Wejście

Na standardowym wejściu podano następujące informacje. Pierwszy wiersz zawiera liczbę robotów $N$ ($1 \le N \le 1,000,000$). Drugi zawiera dwie liczby całkowite $R,M$, określające zasięg obserwacji i pozycje na okręgu ($1 \le R,M \le 10^9$, $N \le M \le 2RN$). Następny wiersz zawiera $N$ różnych liczb całkowitych $x_i$ ($0 \le x_i \le M-1$, $i=1,\ldots,N$), oddzielonych spacjami, oznaczających początkowe pozycje robotów.

Podzadania

• Podzadanie 1: 10 ze 100 punktów; $M \le 10$.

• Podzadanie 2: 30 ze 100 punktów; $N \le 7,000$.

• Podzadanie 3: 60 ze 100 punktów; brak ograniczeń poza pierwotnymi.

Wyjście

Wypisz na standardowe wyjście najmniejszą możliwą maksymalną odległość przemieszczenia robotów, tak aby obserwować cały okrąg.

Przykład

Wejście 1

3
2 10
1 2 5

Wyjście 1

1

Wejście 2

6
1 11
0 1 2 3 4 5

Wyjście 2

2