33486번 - $\mathtt{MatKor} \oplus \mathtt{AlKor} = \mathtt{MatAl}$ 서브태스크스페셜 저지

문제

이번 대회인 제6회 MatKor Cup은 고려대학교의 정보보호학부 동아리 MatKor와 사이버국방학과 동아리 AlKor가 함께 주최한다. 7회 대회부터는 대회 명칭도 살짝 수정해 <제7회 MatKor&AlKor(MatAl) Cup>으로 열릴 예정이다.

이번 대회부터 MatKor와 AlKor가 공동 주최를 하며, 다음 대회 이름이 MatAl Cup인 만큼, 두 동아리는 금속 현판(Metal Plate)을 만들려고 한다. 이 현판은 길이가 1ドル$인 금속 조각 $N$개를 일렬로 붙여 직선형으로 만들었다. 차례로 1ドル,ドル 2ドル,ドル $\cdots,ドル $N$번 금속 조각을 일렬로 붙여 현판을 만들었다고 할 때, $i$번 금속 조각은 초기에 $A_i$의 온도를 가진다. 그런데 만약 금속 조각의 온도가 크게 차이 나는 두 조각이 이웃해 있으면 현판이 쪼개질 수 있다는 사실을 알게 된 민재는 금속 조각을 가열해 이웃한 두 금속 조각의 온도 차이를 $M$이하로 만들고자 한다. 민재는 금속 조각을 한 번 가열할 때 아래 행동을 순서대로 한다.

• 가열할 금속 조각의 번호 $i$를 고른다.
• $i$번째 금속 조각의 온도를 $N$만큼 올리기 위해 가열한다. 이때, 현판은 다음과 같이 가열된다.
  • 모든 조각들의 온도가 증가하는데, 가열하는 위치로부터 떨어진 조각의 개수만큼 증가하는 온도가 감소한다. 즉, 아래 수식과 같다.
  • 모든 정수 1ドル\le j\le N$에 대해, $j$번째 금속 조각의 온도는 $N-\left| i-j \right|$만큼 증가한다.

민재는 위의 행동을 최소한으로 하여 이웃한 두 금속 조각의 온도 차이를 $M$이하로 만들고자 한다. 즉, 모든 정수 1ドル\le i<N$에 대하여 $\left| A_i-A_{i+1} \right|\le M$을 만족하도록 해야 한다.

민재의 최소 행동 횟수와 실제 행동을 찾아보자.

입력

첫 번째 줄에 금속 현판의 길이 $N(1\le N\le 10^6),ドル 인접한 두 조각의 최대 온도 차이 목표 $M(0\le M\le 10^9)$이 공백으로 구분되어 주어진다.

두 번째 줄에 현판을 이루는 각 금속 조각의 초기 온도 $A_1, A_2, \cdots, A_N(1\le A_i\le 10^9)$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 목표를 달성하기 위한 최소 행동 횟수 $L$을 출력한다. 만약 불가능한 경우 -1을 대신 출력한다.

만약 목표를 달성할 수 있다면, 두 번째 줄에 최소 횟수로 가열할 때 $i$번째 금속 조각을 가열하는 횟수를 순서대로 공백으로 구분하여 출력한다. 가능한 방법이 여러 가지일 경우, 아무거나 출력해도 된다.

제한

서브태스크

힌트