Zəngli saat
Hər gecə yatmazdan əvvəl Kostya zəngli saatlarını qurur ki, səhəri gün bütün günü yatıb qalmasın. Hər bir zəngli saat dəqiq bir dəqiqədə çalır və gecə yarısından sonra işə düşdüyü dəqiqənin nömrəsi ilə, yəni tam ədəd a[i] ilə təyin olunur. Zəngli saatlar müvafiq dəqiqənin əvvəlində çalır və dəqiqə ərzində çalır.
Kostya dəqiq olaraq oyanacaq, əgər müəyyən m ardıcıl dəqiqələrdə ən azı k zəngli saat çalarsa. Qeyd edək ki, Kostya yalnız həmin zaman intervalında çalmağa başlayan zəngli saatları nəzərə alır. Əvvəllər çalmağa başlayan, lakin həmin intervalda çalmağa davam edən zəngli saatları Kostya nəzərə almır.
Kostya o qədər yorğundur ki, bütün günü yatmaq və oyanmamaq istəyir. Kostyanın bütün növbəti günü yatıb qalması üçün neçə zəngli saatı söndürməli olduğunu müəyyən edin. Başlanğıcda bütün zəngli saatların açıq olduğunu düşünün.
Giriş məlumatları:
Birinci sətirdə üç ədəd n, m, k (1 ≤ k ≤ n ≤ 10^5, 1 ≤ m ≤ 10^6) — zəngli saatların sayı və Kostyanın oyanması üçün parametrlər (müddət və zəngli saatların sayı). İkinci sətirdə n müxtəlif ədədlər a[1], a[2],...,a[n] (1 ≤ a[i] ≤ 10^6), burada a[i] i-ci zəngli saatın işə düşdüyü dəqiqəyə bərabərdir. Ədədlər təsadüfi qaydada verilmişdir. Kostyanın yaşadığı planetdə günün 10^6 dəqiqə olduğunu düşünün.
Çıxış məlumatları:
Kostyanın bütün növbəti günü yatıb qalması üçün neçə zəngli saatı söndürməli olduğunu müəyyən edin.
İzah:
Birinci nümunədə Kostya üçüncü dəqiqədə çalan ilk zəngli saatı söndürmək kifayətdir.
İkinci nümunədə Kostya heç bir zəngli saatı söndürməyə ehtiyac yoxdur, çünki heç bir 10 ardıcıl dəqiqədə 3 zəngli saat çalmır.
Üçüncü nümunədə Kostya yuxusunu davam etdirmək üçün istənilən 6 zəngli saatı söndürməlidir.