Giải bài trực tuyến

Anh Phạm Quang Vũ đang tính thử CD nhạc để tặng bạn Liên Trà. Vì vậy anh ta quyết định mua một số đĩa nhạc.

Quang Vũ có 1 bộ sưu tập những bài hát dân ca trên máy tính, gồm N bài đánh số từ 1 đến N. Bộ sưu tập quá lớn đến nỗi mà tất cả bài hát ko thể hiện thị 1 lần trên khung hiển thị; chính vì thế, khi 1 bài hát đang chạy thì chỉ có K bài trong sộ sưu tập hiển thị trên màn hình. Dĩ nhiên, K bài hát bao gồm cả bài đang chơi. Khi 1 bài hát xuất hiện trên khung hiển thị, phần mềm cần thêm vào các file của nó trong ổ đĩa và đọc các thông tin như nghệ sĩ và tên bài hát. Những thông tin này được lưu trữ trong bộ nhớ máy tính, cho nên nếu bài hát xuất hiện lại trên khung hiển thị, ko cần mở lại file đó nữa.

Viết chương trình, biết số bài hát Quang Vũ muốn nghe, theo thứ tự anh ta muốn. Với mỗi bài hát, tìm cặp bài hát hiện lên khi 1 bài đang được chơi (sẽ thêm khoảng giữa 2 bài này, kể cả chúng), để tổng số file cần thêm vào trên ổ đĩa là nhỏ nhất có thể.

Input:

Dòng đầu tiên gồm 2 số nguyên N và K (1 <= K <= N <= 1 000 000 000), số bài hát trong bộ sư tập và số bài hiển thị được.

Dòng thứ 2 gồm số nguyên M (1 <= M <= 300 000), số bài hát Quang Vũ muốn nghe

M dòng tiếp theo gồm thứ tự chơi nhạc mà Quang Vũ muốn. Tất cả các số đều phải từ 1 đến N, và ko có bài nào lặp lại.

Output:

Output gồm 1 dòng duy nhất cho biết số file cần thêm vào nhỏ nhất có thể khi đang chơi nhạc trong danh sách bài nhạc của Quang Vũ.

Ví dụ:

Dữ liệu:

10 3
5
4
5
8
7
6

Kết quả:

5