Tại sân chơi trí tuệ Bách Khoa, mỗi màn chơi diễn ra như sau: Trên bảng có ~m~ số nguyên dương có giá trị không quá ~n~ được ghi sẵn - tất cả người chơi đều nhìn thấy. Lần lượt từng người chơi phải chọn ~(m-s)~ số từ ~m~ số trên bảng, sau đó tự thêm đúng ~s~ số mới để ghép lại thành một dãy gồm ~m~ số nguyên có giá trị liên tiếp. Nếu một giá trị xuất hiện nhiều lần trên bảng, vẫn chỉ được dùng một lần trong dãy số.

Có một quy tắc bắt buộc: dãy số của mỗi người tạo ra phải khác với tất cả các dãy số mà những người trước đó đã tạo ra. Người nào tạo được dãy số hợp lệ và chưa từng xuất hiện thì qua màn. Người không tạo được thì bị loại, và màn chơi kết thúc.

Yêu cầu: Cho ~m~ số trên bảng, hãy dự đoán tối đa bao nhiêu người có thể qua được màn chơi này?

Input

• Dòng 1: ba số nguyên ~n~, ~m~ và ~s~ ~(1 \le n \le 10^9; 1 \le s < m \le 10^5)~.

• Dòng 2: ~m~ số nguyên, mỗi số từ ~1~ đến ~n~ – giá trị các số trên bảng.

Output

• In số lượng dãy số khác nhau gồm các số nguyên liên tiếp có thể tạo được.

Scoring

Sample Input 1

10 5 2
7 1 3 5 6

Sample Output 1

5

Sample Input 2

11 6 2
5 5 5 5 5 5

Sample Output 2

0

Notes

• Ví dụ 1: Các dãy số có thể tạo ra: 1 2 3 4 5; 2 3 4 5 6; 3 4 5 6 7; 4 5 6 7 8; 5 6 7 8 9.

• Ví dụ 2: Không thể tạo thành dãy số hợp lệ.