최소 변동 구간 선택

사진 스트립에서 $N$장의 사진이 일렬로 주어지고, 각 사진에는 정수 점수 $h_i$가 매겨져 있다. 당신은 사진의 순서를 유지한 채로 정확히 $M$장을 골라 하이라이트를 구성하려고 한다. 선택한 $M$장의 총합은 최소 목표 $S$ 이상이어야 하며, 인접하게 선택된 사진들 사이의 점수 차이의 절댓값들 중 최댓값을 가능한 한 작아야 한다. 이때 그 최댓값을 최소로 만드는 선택이 여럿이면, 선택된 사진의 인덱스 수열이 사전순으로 가장 앞선 것을 채택한다. 목표는 그러한 최소 최댓값과 그때의 인덱스 수열을 결정하는 것이다.

첫째 줄에 정수 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 200000$, $1 \le M \le N$) 둘째 줄에 정수 $S$가 주어진다. ($-10^{18} \le S \le 10^{18}$) 셋째 줄에 $N$개의 정수 $h_1, h_2, \ldots, h_N$가 공백으로 구분되어 주어진다. ($-10^{9} \le h_i \le 10^{9}$) 모든 입력 값은 64비트 부호 있는 정수 표현 범위 내에 있다. 사진은 1번부터 $N$번까지의 인덱스를 가진다. 선택한 인덱스 수열은 엄밀히 증가해야 한다. 입력은 공백은 한 칸 이상, 줄바꿈은 표준 개행 문자로만 주어진다. 추가적인 공백 문자는 없다.

만약 조건을 만족하는 선택이 존재하지 않으면, 첫째 줄에 -1만 출력하고 추가 출력은 하지 않는다. 조건을 만족하는 선택이 존재하면, 첫째 줄에 인접하게 선택된 사진들의 점수 차이의 절댓값들 중 최댓값의 최소값을 나타내는 정수 $D_{min}$을 출력한다. 둘째 줄에 사전순으로 가장 앞서는 해당 선택의 인덱스 수열 $i_1, i_2, \ldots, i_M$을 공백으로 구분하여 출력한다. ($1 \le i_1 < i_2 < \cdots < i_M \le N$) 정수 출력에는 불필요한 선행 0을 사용하지 않는다. 불필요한 공백을 출력하지 않으며, 각 줄 끝에는 개행 문자를 정확히 하나 출력한다.