Số thao tác giúp mảng tăng dần 2.

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Cho dãy số A[] gồm có N phần tử. Ở mỗi thao tác bạn có thể tăng các phần tử trong mảng lên 1 lượng là d đơn vị, hãy xác định số thao tác tối thiểu sao cho mảng trở thành một dãy tăng chặt. Ví dụ dãy 1 2 3 7 8 là một dãy tăng chặt, nhưng dãy 1 2 2 7 8 không phải là một dãy tăng chặt. Ví dụ với mảng ban đầu là 1 3 3 2 và d = 2, ta cần thực hiện thao tác thứ nhất thêm d vào phần tử thứ 3 trong mảng, mảng trở thành 1 3 5 2, ta tiếp thục thực hiện 2 thao tác thêm d vào phần tử thứ 4, mảng trở thành dãy tăng chặt là 1 3 5 6

Input

Dòng đầu tiên là số nguyên N và số d. Dòng tiếp theo gồm N số nguyên A[i].(1≤ N, d ≤ 10^4; 0 ≤ A[i] ≤ 10^6)

Output

In ra số thao tác tối thiểu cần thực hiện để biến mảng thành dãy tăng chặt.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

5 2
1 2 1 3 6

Output

2

Thông tin học tập

• Buổi: B09
• Concepts: 1D arrays, input, traversal, aggregation
• Giới hạn kiến thức: B01-B09
• Time limit: 2 seconds
• Memory limit: 20 MB
• Point: 10