Nam đang bị cuốn vào một trò chơi DOMINO với luật chơi được phát triển từ tính chất của những quân DOMINO ngoài đời thực.

Ban đầu, trò chơi có ~N~ quân DOMINO, quân DOMINO thứ ~i~ có chỉ số đứng vững là ~t_i~, nghĩa là vào giây thứ ~t_i~ (bắt đầu chơi trò chơi là giây thứ ~0~) thì quân DOMINO thứ ~i~ này sẽ bị đổ sang phải và chỉ làm đổ quân DOMINO thứ ~i+1~ ~(i < N)~ vào giây thứ ~t_i+1~. Tất nhiên nếu quân DOMINO thứ ~i+1~ đã đổ trước đó thì xem như không có gì xảy ra cả.

Ở level đầu tiên của trò chơi, trò chơi yêu cầu Nam đưa ra thời gian ngắn nhất để tất cả các quân DOMINO bị đổ hết. Với ~N=6~ và các quân DOMINO có chỉ số đứng vững tính từ trái qua phải là ~[3,11,4,15,12,2]~ thì Nam đã nhanh chóng trả lời được kết quả chính là ~6~. Giải thích cho kết quả này, Nam nhận xét quân DOMINO thứ ~5~ sẽ bị đổ sau cùng vì trước đó có quân DOMINO thứ ~3~ bị đổ ở giây ~4~, ngay sau đó quân thứ ~4~ sẽ bị đổ ở giây thứ ~5~ dẫn đến việc quân thứ ~5~ sẽ đổ ở giây thứ ~6~.

Như vậy Nam đã vượt qua level một, vấn đề trở nên phức tạp hơn nhiều khi trò chơi cung cấp cho Nam một giá trị ~D~ chính là số lượng những bức tường chắn đặt vào giữa vị trí hai quân DOMINO liên tiếp.

Khi đặt một bức tường chắn vào giữa hai quân DOMINO ~i~ và ~i+1~ ~(i < N)~, vào thời điểm DOMINO thứ ~i~ bị đổ, quân thứ ~i+1~ sẽ không hề bị ảnh hưởng (do bị cản bởi bức tường chắn), khi đó trò chơi vẫn tính quân DOMINO thứ ~i~ đã bị đổ nhưng sẽ không có bất kì tác động nào đến quân DOMINO thứ ~i+1~.

Trò chơi còn cung cấp thêm một giá trị thời gian ~T~ và yêu cầu Nam đưa ra được chiến lược tối ưu để chèn nhiều nhất ~D~ bức tường chắn vào ~N-1~ vị trí giữa hai quân DOMINO liên tiếp sao cho vào thời điểm ~T~ sẽ có ít quân DOMINO bị đổ nhất. Bắt đầu level này, trò chơi cung cấp ~3~ con số ~N=5, D=2~ và ~T=5~ kèm theo các chỉ số đứng vững ~t_i~ từ trái qua phải là ~[1,9,4,6,7]~. Nam quyết định chèn một bức tường chắn vào giữa quân thứ ~1~ và quân thứ ~2~, một bức tường chắn vào giữa quân thứ ~3~ và quân thứ ~4~. Kết quả là tại thời điểm ~T=5~, chỉ có ~2~ quân DOMINO bị đổ, đó là quân thứ ~1~ và quân thứ ~3~, kết quả này chính xác và đã giúp Nam bước vào vòng trong của level này.

Nhưng đến đây, trò chơi lại liên tục đưa ra những bộ số ~N,D,T~ quá lớn khiến cho Nam không kịp tính toán trong thời gian ~1~ giây cho phép.

Yêu cầu: Bạn hãy viết chương trình giúp Nam thực hiện tính kết quả tối ưu là số quân DOMINO bị đổ ít nhất với ~N,D~ và ~T~ cho trước trong thời gian một giây nhé!

Input

• Dòng đầu tiên chứa ba số nguyên ~N,D~ và ~T~ lần lượt là số lượng quân DOMINO, số lượng bức tường chắn và thời điểm mà trò chơi yêu cầu dừng lại ~(1 \le N,D \le 2 \cdot 10^6, 1 \le T \le 10^9)~.

• Dòng thứ hai gồm ~N~ số nguyên ~t_1,t_2,\dots,t_N~ lần lượt là các chỉ số đứng vững của ~N~ quân DOMINO đó ~(1 \le t_i \le 10^9)~.

Output

Một số nguyên là số lượng quân DOMINO bị đổ ít nhất vào thời gian ~T~.

Scoring

Sample Input 1

5 2 5
1 9 4 6 7

Sample Output 1

2

Sample Input 2

5 1 42
13 37 47 11 42

Sample Output 2

4

Sample Input 3

2 1 10
10 9

Sample Output 3

2