도시 자전거

도시 자전거는 널리 쓰이는 출퇴근 수단이다. 일부 거치대에는 자전거가 몇 대뿐이고 다른 거치대는 거의 가득 차 빈 자리가 거의 없어서, 이용자에게 불편을 준다. 자전거 회사는 이런 편차를 줄이려고 정기적으로 트럭을 보내 거치대 사이에서 자전거를 옮긴다.

트럭 한 대가 자전거 센터를 떠나 재배치 운행을 시작하려 한다. 트럭은 최대 $c$대의 자전거를 실을 수 있다. 출발 전에 트럭은 초기 적재량을 $0$대 이상 $c$대 이하로 고를 수 있다. 이후 트럭은 $n$개의 거치대를 순서대로 방문한다. 각 거치대는 최대 $d$대의 자전거를 거치할 수 있고, 운행 시작 시점에 각 거치대에는 이미 자전거가 일부 거치되어 있다. 트럭은 각 거치대에서 트럭의 용량 $c$와 거치대의 용량 $d$를 넘지 않는 범위 안에서 자전거를 원하는 만큼 싣거나 내릴 수 있다. 운행이 끝났을 때 트럭의 적재량이 초기 적재량과 같을 필요는 없다. 목표는 어떤 거치대든 자전거 수의 최댓값과 최솟값의 차이를 최소화하는 것이다.

달성할 수 있는 최소 차이는 얼마인가?

첫 번째 줄에 세 정수 $n$, $d$, $c$ ($2 \le n \le 2 \cdot 10^5$, $1 \le d, c \le 10^6$)가 주어진다. 각각 거치대의 개수, 거치대의 용량, 트럭의 용량이다. 이어지는 $n$개의 줄에는 각각 $0$ 이상 $d$ 이하의 정수 하나가 주어지며, $i$번째 값은 거치대 $i$에 처음 거치된 자전거 수다.

달성할 수 있는 최소 차이를 정수 하나로 출력한다. 차이는 어떤 거치대든 자전거 수의 최댓값과 최솟값의 차이를 뜻한다.