UCROOS2


Submit solution

Points: 11
Time limit: 1.0s
Memory limit: 512M

Problem type

Con đường dài qua trang trại của Farmer John có \(N\) điểm băng qua, được đánh số thuận tiện từ 1 đến \(N\). Để cho phép bò qua đường tại những điểm băng qua này, FJ lắp đặt các tín hiệu giao thông điện tử, đèn sáng với biểu tượng bò xanh khi bò có thể qua đường, và đỏ khi không thể đi.

Thật không may, một cơn bão điện lớn đã làm hỏng M tín hiệu của ông tại các điểm \(x_1,x_2,…,x_M\).

Yêu cầu: Tính số lượng tối tiểu các tín hiệu mà FJ cần sửa chữa để có ít nhất một đoạn liên tục dài ít nhất \(K\) tín hiệu hoạt động.

Input

  • Dòng đầu tiên chứa các số \(K,M (1 ≤ K, M ≤ N, 1 ≤ N ≤ 100000)\).

  • Các dòng tiếp theo, mỗi dòng mô tả số vị trí của một tín hiệu bị hỏng.

Output

In ra số lượng tín hiệu tối thiểu cần sửa chữa để có một đoạn liên tục dài ít nhất K tín hiệu hoạt động ở đâu đó trên con đường.

Sample Intput

10 6 5
2
10
1
5
9

Sample Output

1

Comments

There are no comments at the moment.