#61 increasing

Loading problem...

Preparing the statement, recent submissions, and submit form.

#61 increasing | DOJ

Authors: lunarlity

Statement

길이 $N$ 의 정수 수열 $A=[A_1,A_2,\ldots,A_N]$ 과 정수 $K$ 가 주어진다.

당신은 다음 연산을 원하는 만큼 수행할 수 있다.

$1\le i\le N$ 을 만족하는 정수 $i$ 를 하나 고른 뒤, $A_i$ 를 $A_i+K$ 로 바꾼다. $K<0$ 인 경우, 이 연산은 $A_i$ 에서 $|K|$ 를 빼는 것과 같음에 유의하라.

당신의 목표는 수열이 다음 조건을 만족하게 만드는 것이다.

$A_1 < A_2 < \cdots < A_N$

필요한 연산 횟수의 최솟값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ K$ $A_1\ A_2\ \cdots \ A_N$

조건을 만족하게 만들기 위해 필요한 연산 횟수의 최솟값을 출력한다.

Sample 1

Input

3 2
4 1 3

Output

Sample 2

Input

3 -2
4 1 3

Output