Kích hoạt Redstone


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Austin đang xây dựng một hệ thống đèn chiếu sáng dọc đường cho thành phố của cậu trong Minecraft. Cậu dự định sẽ đặt $N$ đèn chiếu sáng trên một trục đường tại các vị trí $x_1,x_2,...,x_N$ (không có 2 đèn ở cùng một vị trí). Cậu sẽ cần đặt các đuốc redstone tại vị trí một số đèn chiếu sáng. Đuốc redstone sẽ giúp kích hoạch đường dây redstone. Một đuốc redstone có thể kích hoạt redstone tối đa trong phạm vi $M$ khối. Điều này có nghĩa một đèn chiếu sáng sẽ được kích hoạt nếu khoảng cách giữa nó và đuốc redstone gần nhất không quá $M$ (khoảng cách giữa vị trí $a$ và $b$ là $|a-b|$).

Austin muốn chế tạo ít đuốc redstone nhất, vì vậy hãy giúp Austin biết số đuốc redstone cần chế tạo để thắp sáng các ánh đèn dọc trục đường.

Dữ liệu

  • Dòng đầu tiên chứa số nguyên $N,M \ (0 < N ≤ 10^5;0 < M ≤ 10^9)$;
  • Dòng tiếp theo chứa $N$ số nguyên $x_i \ (|x_i| ≤ 10^9)$.

Kết quả

  • Số lượng đuốc redstone ít nhất.

Ví dụ

Ví dụ 1

input

5 1
-1 0 1 3 5

output

3

Comments

There are no comments at the moment.