Mọi chuyện chẳng diễn ra như kế hoạch: tuy tránh được những người bảo vệ trong bảo tàng, bạn lại không để ý rằng camera giám sát có mặt khắp nơi. Kết quả là màn ra mắt với tư cách một tên trộm tác phẩm nghệ thuật trở thành thảm họa: bạn bị bắt và phải vào tù.

Vì Wi-Fi trong tù quá tệ, bạn muốn vượt ngục. Xem nhiều phim về nhà tù, bạn biết rằng việc đánh lạc hướng là yếu tố then chốt của mọi kế hoạch vượt ngục. Vì vậy, bạn quyết định tổ chức một cuộc nổi loạn để làm mồi nhử.

Có \(N\) buồng giam nằm dọc theo một hành lang. Buồng ngoài cùng bên trái mang số \(1\), buồng ngay bên phải mang số \(2\), và cứ thế tiếp tục. Không phải mọi bạn tù đều tham gia nổi loạn đúng như kế hoạch, nhưng bạn đã bảo đảm rằng người tù ở buồng \(i\) dự định bắt đầu nổi loạn vào thời điểm \(t_i\), tức đúng \(t_i\) giây kể từ bây giờ. Ngoài ra, mỗi khi nghe thấy người tù ngay bên trái nổi loạn, một người tù cũng sẽ bắt đầu nổi loạn chỉ sau một giây, trừ khi người đó đã nổi loạn rồi. Một khi đã bắt đầu, người tù sẽ không ngừng nổi loạn.

Vào thời điểm \(T\), đại diện địa phương của F.R.U.IT.T.Ar.T. — Cơ quan Đăng ký Liên bang dành cho những chuyên gia công nghệ thông tin bất mãn chuyển nghề sang trộm tác phẩm nghệ thuật — sẽ đến thanh tra. Bạn cho rằng đây là thời điểm hoàn hảo để trốn thoát. Tuy nhiên, các quản giáo không muốn có nổi loạn trong lúc thanh tra. Bạn lo rằng họ sẽ dùng \(D\) tấm đệm cách âm có thể lắp giữa các buồng giam. Nếu đặt một tấm đệm giữa buồng \(i-1\) và buồng \(i\), người tù ở buồng \(i\) sẽ không bắt đầu nổi loạn trước thời điểm \(t_i\), bất kể hành động của người tù ở buồng \(i-1\) hay bất kỳ người tù nào khác.

Hãy viết chương trình giúp bạn ước lượng khả năng thành công: tính số người tù ít nhất đang nổi loạn tại thời điểm \(T\) nếu các quản giáo đặt đệm một cách tối ưu.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(N\), \(D\) và \(T\): số buồng giam, số tấm đệm và thời điểm đại diện đến thanh tra.

Dòng thứ hai chứa \(N\) số nguyên \(t_i\), trong đó \(t_i\) là thời điểm người tù ở buồng \(i\) dự định bắt đầu nổi loạn.

Dữ liệu ra

In đúng một số nguyên trên một dòng: số người tù ít nhất đang nổi loạn tại thời điểm \(T\).

Ràng buộc

• \(1\le N,D\le2\,000\,000\).
• \(D<N\) trong mọi bộ dữ liệu.
• \(1\le T\le10^9\).
• \(1\le t_i\le10^9\) với mọi \(i=1,\ldots,N\).

Phân nhóm

1. \(15\) điểm: \(N\le500\).
2. \(10\) điểm: \(N\le500\,000\), \(D=1\).
3. \(20\) điểm: \(N\le4\,000\).
4. \(10\) điểm: \(N\le75\,000\), \(D\le15\).
5. \(25\) điểm: \(N\le75\,000\).
6. \(20\) điểm: không có ràng buộc thêm.

Ví dụ

5 1 42
13 37 47 11 42

4

5 2 5
1 9 4 6 7

2

Giới hạn

Thời gian: \(1{,}5\) giây. Bộ nhớ: \(512\) MiB.