UCROOS2
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