Последовательность a0, a1, ..., at - 1 называется возрастающей если ai - 1 < ai для всех i: 0 < i < t.
Вам задана последовательность b0, b1, ..., bn - 1 и натуральное число d. Каждый ход выбирается один из элементов последовательности и увеличивается на d. Какое минимальное число ходов необходимо совершить, чтобы сделать последовательность возрастающей?
Первая строка входных данных содержит два натуральных числа n и d (2 ≤ n ≤ 2000;1 ≤ d ≤ 106). Вторая строка содержит элементы последовательности b0, b1, ..., bn - 1 (1 ≤ bi ≤ 106). Числа в строках разделяются пробелами.
Выведите искомое наименьшее количество ходов.
4 2
1 3 3 2
3
| Codeforces Beta Round 11 |
|---|
| Закончено |
