← 返回题目列表

Codeforces · 11/A

A. 递增序列

中文机器翻译题面 查看原题

如果对于每个 i: 0 < i < t,ai - 1 < ai,则序列 a0, a1, ..., at - 1 称为递增序列。

给定一个序列 b0, b1, ..., bn - 1 和一个正整数 d。在每一步中,您可以选择给定序列的一个元素并将 d 添加到其中。使给定序列递增所需的最少移动次数是多少?

输入

输入的第一行包含两个整数 n 和 d (2 ≤ n ≤ 2000, 1 ≤ d ≤ 106)。第二行包含空格分隔的序列 b0, b1, ..., bn - 1 (1 ≤ bi ≤ 106)。

输出

输出使序列递增所需的最小移动次数。

示例

输入 #1

4 2
1 3 3 2

输出 #1

3