如果对于每个 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