승호는 각종 타임어택 대회의 5관왕이다.

승호가 보유한 타이틀은 다음과 같으며, 모두 1위를 했다:

짜장면 빨리 먹기, 컴퓨터 빨리 조립하기, 큐브 빨리 맞추기, 카드 빨리 쌓기, 그리고 여자친구 빨리 만들기(특히 이 대회에서 우승할 때는 신기록을 갈아치웠다고 한다.)

오늘 또 다른 타임어택 대회가 있다. 이 대회의 이름은 수열 빨리 바꾸기인데, 규칙은 다음과 같다. n개의 수열의 원소가 차례대로 주어진다.

승호와 참가자들은 위치에 상관없이 한 가지 원소를 다른 값으로 바꾸는데 1초의 시간이 걸린다.

참가자들의 목적은 최대한 빨리 공차가 k인 등차수열을 만드는 것이다.

공차가 k인 등차수열이란, 모든 인접한 두 원소를 고려할 때, 오른쪽 원소-왼쪽 원소 = k를 만족하는 수열이다.

예를 들어 처음에 주어진 수열이 [1, 2, 5]이고, k = 2라고 하자.

첫번째 수와 세번째 수를 0, 4로 바꾸는데 2초가 걸리며, [0, 2, 4]는 공차가 2인 등차수열이 된다.

그러나 이렇게 하지 않고, 두 번째 수를 3으로 바꾸면 1초밖에 걸리지 않는다.

이렇게 해서 만들어진 [1, 3, 5]도 공차가 2인 등차수열이다.

0초만에 등차수열을 만드는 방법이 없으므로, 1초 걸려서 공차가 2인 등차수열을 만든 경우가 우승이다.

승호의 6관왕 타이틀을 위해, 공차 k와 수열의 원소들이 주어졌을 때, 우승하는데 걸리는 가장 적게 걸리는 시간을 출력하는 프로그램을 작성하라.

타임어택 timer 2s memory 256MB

타임어택 2s 256MB