30825번 - 건공펀치 등차수열

문제

서울시립대학교의 마스코트와도 같은 존재인 건공이는 어떤 수열을 주더라도 공차가 $K$인 등차수열로 만들어 버리는 버릇이 있다.

건공이는 주어진 수열을 등차수열로 만들기 위해, 건공펀치를 1회 사용하여 수열의 한 원소의 값을 1 증가시킬 수 있다.

건공이는 건공펀치를 최소로 사용하고 싶어하지만, 수열의 길이가 너무 길어 건공펀치의 최소 사용 횟수를 구하는 데 어려움을 겪고 있다.

건공이를 대신하여 주어진 수열을 등차수열로 만드는 데 필요한 건공펀치의 최소 사용 횟수를 구해보자.

입력

첫 번째 줄에 수열의 길이 $N$과 공차 $K$가 공백으로 구분되어 주어진다. (2ドル \le N \le 200\ 000,ドル 1ドル \le K \le 200\ 000$)

두 번째 줄에 수열 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. (1ドル \le A_i \le 100\ 000$)

출력

주어진 수열을 공차가 $K$인 등차수열로 만드는 데 필요한 건공펀치의 최소 사용 횟수를 출력한다.

제한

힌트