18191번 - 피아노 연주

문제

N개의 손가락을 가진 세빈이는 한 손만으로 모든 곡을 연주할 수 있는 최고의 피아니스트다.

세빈이의 두 인접한 손가락 사이의 거리는 K로 일정하다. 고로 i번째 손가락과 첫 번째 손가락 사이의 거리를 X_i라고 한다면, X_i = (i-1)K가 성립한다(1 ≤ i ≤ N).

세빈이는 M개의 음으로 이루어진 곡을 연주하려 한다. 이때 각각의 음을 어떤 손가락으로 연주하는지에 따라 곡을 연주하는 것이 쉬워질 수도, 어려워질 수도 있다.

i번째 음의 음높이를 P_i라 하고, 이 음을 F_i번째 손가락으로 연주한다 하자. i번째 음과 이와 인접한 (i+1)번째 음을 연주할 때의 난이도는 |(P_i+1 - P_i) - (X_Fi+1 - X_Fi)|다.

곡의 난이도는 인접한 두 음을 연주할 때의 난이도의 최댓값으로 정의한다. 각각의 음을 어떤 손가락으로 연주할지 결정하여 곡의 난이도를 최소화하는 프로그램을 작성하시오.

입력

첫 번째 줄에 세빈이의 손가락의 수와 곡을 이루는 음의 수를 나타내는 두 자연수 N과 M, 두 인접한 손가락 사이의 거리를 나타내는 자연수 K가 사이에 공백을 두고 주어진다.

두번째 줄에는 M개의 정수 P₁, ···, P_M이 사이에 공백을 두고 주어진다.

출력

첫 번째 줄에 곡의 난이도의 최솟값을 출력한다.

제한

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 2 × 10⁵
• 2 ≤ M ≤ 2 × 10⁵
• 1 ≤ K ≤ 10⁹
• X_N ≤ 10⁹
• 1 ≤ P_i ≤ 10⁹ (1 ≤ i ≤ M)

힌트