시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB149383235.556%

문제

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

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

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

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

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

입력

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

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

출력

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

제한

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

  • 1 ≤ N ≤ 2 × 105
  • 2 ≤ M ≤ 2 × 105
  • 1 ≤ K ≤ 109
  • XN ≤ 109
  • 1 ≤ Pi ≤ 109 (1 ≤ i ≤ M)

예제 입력 1

5 4 3
7 2 9 3

예제 출력 1

1

F1 = 3, F2 = 1, F3 = 3, F4 = 1.

출처

High School > 경기과학고등학교 > 나는코더다 2019 송년대회 G번