ATM Gạo 2

Xem PDF

Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Trong những ngày giãn cách xã hội, công ty ABC có mở một cây ATM gạo làm từ thiện cho những người dân gặp khó khăn. Hiện nay mới sáng sớm, số lượng người đăng ký đã đến rất đông và tuân thủ xếp thành 1 hàng dài người giãn cách 2 mét với người phía trước.

Qua khảo sát, bộ phận giám sát của công ty phát hiện một số người tình nghi có dấu hiệu "đi xe hơi, đeo vòng vàng" tới xin gạo.

Bộ phận này muốn kiểm tra thông tin liền chụp \(n\) bức ảnh gửi về bộ phận xác minh làm rõ để phê bình công khai. Bức ảnh thứ \(i\) chứa người ở vị trí \(a_{i}\) và tất các bức ảnh với độ rộng vừa đủ cho \(k\) người liên tiếp trong hàng. Bộ phận xác minh sẽ lọc tất cả những người có xuất hiện trong ảnh ra để điều tra.

Hãy xác định số người ít nhất mà bộ phận xác minh phải thực hiện điều tra.

Input

  • Dòng đầu tiên chứa \(3\) số nguyên dương \(m, n, k\) (\(n,k \leq m\)).
  • Dòng thứ \(2\) chứa \(n\) số nguyên \(a_{1},a_{2},...,a_{n}\) (\(1 \leq a_{i} \leq m\)).

Output

  • Ghi ra \(1\) số nguyên duy nhất là số người tối thiểu mà bộ phận xác minh phải thực hiện điều tra.

Constraints

  • \(1 \leq n \leq 2.10^{5}\)
  • \(1 \leq k \leq m \leq 10^{9}\)

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(k=2; m \leq 5.10^{3}\).
  • Subtask \(2\) (\(30\%\) số điểm): \(2 \leq k \leq m; m \leq 5.10^{3}\).
  • Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
10 6 4
4 7 2 8 1 9 
Output
8

Test 2

Input
10 6 4
4 7 2 5 1 9 
Output
9
Note
  • Trong ví dụ thứ \(1\), chụp các bức ảnh [\(1,4\)], [\(7,10\)] lặp lại.
  • Trong ví dụ thứ \(2\), chụp các bức ảnh [\(1,4\)], [\(2,5\)], [\(6,9\)] lặp lại.

Bình luận


  • 0
    VietCT    9:58 p.m. 20 Tháng 8, 2020

    Sao lại có test đáp án lại còn lớn hơn cả số người nhỉ 🙂

    Có test đáp án ra 6218 mà m có 2502

    • 1 bình luận nữa