Szarlotka

Szarlotka

Limit pamięci: 32MB

Profesor Vistosław Windobit po powrocie do domu postanowił zorganizować przyjęcie dla całego sąsiedztwa. Zamówił n kawałków swojego ulubionego ciasta, czyli szarlotki. Tuż przed przyjęciem okazało się, że nie wszystkie kawałki szarlotek mają takie same rozmiary. Goście są bardzo wrażliwi na tym punkcie, a więc każdy kawałek szarlotki na przyjęciu może być co najwyżej o k większy od każdego innego. Profesor Vistosław poprosił Ciebie, swojego najlepszego doktoranta, abyś rozwiązał ten problem. Musisz wyznaczyć jak największy podzbiór kawałków szarlotki, w którym każdy kawałek jest co najwyżej o k większy od każdego innego.

Zadanie:

    Napisz program, który:
  • wczyta opis kawałków szarlotek i liczbę k
  • wyznaczy moc największego podzbioru kawałków szarlotek, w którym każdy kawałek jest co najwyżej o k większy od każdego innego
  • wypisze wynik na standardowe wyjście

Wejście:

W pierwszej linii znajdują się dwie liczby całkowite: n i k (1 <= n <= 5000000; 0 <= k <= 1000000). W następnej linii znajduje się n liczb całowitych, mieszczących się w przedziale <1; 1000000> - są to rozmiary dostępnych kawałków szarlotki.

Wyjście:

Jedna liczba, będąca mocą największego podzbioru kawałków szarlotek, w którym każdy kawałek jest co najwyżej o k większy od każdego innego.

Przykład:

wejście:
5 3
13 2 2 8 5

wyjście:
3

Wyjaśnienie przykładu:

Największym podzbiorem kawałków szarlotek dla tego przykładu byłby zbiór: {2, 5, 2}.